Opkg upgrade path proposal

Tick Chen tick at openmoko.com
Mon Dec 8 10:56:03 CET 2008


----- Forwarded message from Tick Chen <tick at openmoko.com> -----
Sorry, the Subject of last mail if wrong. 
Change it back. 
Sorry
Date: Mon, 8 Dec 2008 17:48:44 +0800
From: Tick Chen <tick at openmoko.com>
To: Opkg devel List <opkg-devel at lists.openmoko.org>
Cc: OLV <olv at openmoko.com>, John Lee <john_lee at openmoko.com>,
	Julian <julian_chu at openmoko.com>, Tick <tick at openmoko.com>,
	Jeremy <jeremy at openmoko.com>, Erin <erin_yueh at openmoko.com>
Subject: mokoko

Hi List, 
  
(CC to devel at lists.openmoko.org. If you want to reply, please reply to opkg-devel at lists.openmoko.org, thank you.)

  Recently I am looking into the upgrade sequence and having the
following ideas. 

1. opkg using pointer array to list upgrade candidates, it takes many
memory operations. (calloc + many realloc + free)
2. opkg upgrade/install packages recursively while check dependency. 
   This takes a long time. 
3. Arrary list is not easy to modify. Cost is high.
4. We have enough information to create the upgrade path before actually
action. (If the dependency in Packages file is correct.) Here we assume
it is correct. 

My proposal of improving this is:
* create a 2D tree. Using struct list_head in Linux kernel.

1.1: list all packages that been installed and need to be upgraded. 
1.2: list packages that been installed and need to be upgraded. 

2: parsing all packages that need to be installed because of the upgrading, and insert them into the list. 
  * check unlisted packages

3: check the dependency and move packages depended by others under the
depened list of the package, that first depended. 
  * provide/conflict/replaced/recommended packages

Example:
We have package:
A B C D E F G H I J K L M N
And  
G H I J are depended by A
M is depended by H
K H L are depened by C
M N are depended by L
I O are depened by J

In current algorithm it will try to install as follow:
A (G H (M) H' I J (O) J') A'  B C (K L) C' D E F G H I J
while installing every package it will check dependency once.

With my proposal it will be:
At step 1 we will get a list of 
. --A--B--C--D--E--F--G--H--I--J--K--L--M--N

On step 2: check all unlisted dependency,
Here we get O
Then the list will becomes:
. --A--B--C--D--E--F--G--H--I--J--K--L--M--N
                               |_O

On step 3:
G H I J will move under A,
because I moved before J therefore I does not move under J
M will move under H
K L will move under C, because H had been moved, that is H is in front
of C, and therefore do not move. So does M to L, and I to J.

Therefore the structure will be 
. --A--B--C--D--E--F
    |     |__k---L
    |            |_ N
    |__G --H --I--J 
           |_M    |_O

The sequence will be: (if down is left arm, after is left arm, from
smallest to largest)
G M H I O J A B K N L C D E F

This way we can reduce many double check of packages, and many memory
operations.

The first version of the active_list structure is in SVN r4855, 
not inegrated into opkg operations yet. 
I am still testing my idea. 

If you have any advice, consideration, or think I am wrong, 
please feel free to help me. :-)
Thank you. 

Cheers, 
Tick



_______________________________________________
opkg-devel mailing list
opkg-devel at lists.openmoko.org
http://lists.openmoko.org/mailman/listinfo/opkg-devel


----- End forwarded message -----
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: Digital signature
Url : http://lists.openmoko.org/pipermail/opkg-devel/attachments/20081208/fff8059b/attachment.pgp 


More information about the opkg-devel mailing list