LinuxQuestions.org
Latest LQ Deal: Latest LQ Deals
Go Back   LinuxQuestions.org > Forums > Linux Forums > Linux - Distributions > Slackware
User Name
Password
Slackware This Forum is for the discussion of Slackware Linux.

Notices


Reply
  Search this Thread
Old 06-05-2010, 12:59 PM   #1
Luiz Ramos
LQ Newbie
 
Registered: Jun 2010
Location: São Paulo - Brazil
Distribution: Slackware, Debian
Posts: 19

Rep: Reputation: 1
Slack 13.1: some trouble with mkinitrd


Hello,

I recently tried - better, are in ways of - upgrading my notebook from Slackware 13.0 to 13.1. There are always some tricky things to wrap around when such upgrade times come, but now I think I caught a bug in mkinitrd, if I'm not wrong.

mkinitd doesn't return when I run:

mkinitrd -c -k 2.6.33.4-smp -s /boot/initrd-tree-2.6.33.4-smp \
-m ext3:ext2:psmouse:usb_storage:ehci_hcd:ohci_hcd \
-f ext3 -r /dev/sda1 -h /dev/sda5 -l br-abnt2 \
-o initrd-2.6.33.4-smp.gz

or similar.

After some debugging, I found that the routine copy-libs() is stuck in an infinite loop, because the statement "while [ "$COUNT" != "0" ]; do" does hold always (that is, COUNT never reaches zero). This, by its side, happens because the set of libs whose dependencies should be checked against are regenerated integrally after each step, and the algorithm doesn't converge.

I could fix the problem adding some code, which removes the libraries found in the iteration "i-1" from the list of files found in the iteration "i". A patch in provided below.

This done, I could build my first initrd image for Slack 13.1 and put
it to run with kernel 2.6.33.4.

Hope this could help Slack community,

Luiz Ramos
São Paulo - Brazil


--- patch start --------------------------
--- a/mkinitrd 2010-05-08 03:42:25.000000000 -0300
+++ b/mkinitrd 2010-06-05 14:26:35.000000000 -0300
@@ -42,6 +42,9 @@
# Add lukskey option (-K). Automatically add kernel modules listed in
# load-kernel-modules if that file is executable.
# Yada yada yada.
+# Fixed by Luiz Ramos 05 June 2010
+# Added code for preventing infinite loop when running copy_libs in
+# some cases.

MKINITRD_VERSION=1.4.5

@@ -196,11 +199,16 @@

find $SOURCE_TREE -type f -exec ldd {} 2>/dev/null \; | unify_libs > $TMPFILE
while [ "$COUNT" != "0" ]; do
+ PREV_FILE=${PRFX}${COUNT}
COUNT=$((COUNT+1))
for i in $(cat $TMPFILE) ; do
ldd $i 2>/dev/null
done | unify_libs > ${PRFX}${COUNT}
TMPFILE=${PRFX}${COUNT}
+ for f in $(cat ${PREV_FILE}) ; do
+ grep -v ${f} ${TMPFILE} >${TMPFILE}_aux
+ mv ${TMPFILE}_aux ${TMPFILE}
+ done
[ $(cat $TMPFILE | wc -l) -eq 0 ] && COUNT=0
done

--- patch end -----------------------------
 
Click here to see the post LQ members have rated as the most helpful post in this thread.
Old 06-05-2010, 04:10 PM   #2
GazL
LQ Guru
 
Registered: May 2008
Posts: 5,022
Blog Entries: 16

Rep: Reputation: 2623Reputation: 2623Reputation: 2623Reputation: 2623Reputation: 2623Reputation: 2623Reputation: 2623Reputation: 2623Reputation: 2623Reputation: 2623Reputation: 2623
Interesting find Luiz, thanks for providing your fix, and welcome to LQ.

I find these sorts of things fun to play with (better than a crossword ) and your post piqued my interest so I took at look at that part of mkinitrd. The existing approach seemed a bit convoluted. so rather than try and patch an already unclear section of code I had a go at rewriting the entire routine using a recursive function.

Here's what I came up with, along with a test case to show it in action. It's not a direct patch for mkinitrd, but it could be slotted in quite easily if someone wanted to.

Code:
#!/bin/bash

function rfind_libs()
{
        file="$1"
        depends="$( ldd "$file" | awk '/=. \// { print $3 }' )"
        if [ -n "$depends" ] ; then
                echo "$depends" | tr " " "\n" 
                for file in $depends
                do
                        rfind_libs "$file"
                done
        fi
}


# TEST CASE:

SOURCE_TREE="/bin"
LIB_LIST="/tmp/lib.list"

rm "$LIB_LIST" >/dev/null 2>&1

while read file
do
       rfind_libs "$file" >> $LIB_LIST
done < <( find "$SOURCE_TREE" -type f )

sort -u $LIB_LIST > $LIB_LIST.sorted && mv $LIB_LIST.sorted $LIB_LIST
If anyone can see any obvious flaws with this approach I'd be interested to know purely from an academic standpoint.
 
Old 06-05-2010, 06:23 PM   #3
Richard Cranium
Senior Member
 
Registered: Apr 2009
Location: Carrollton, Texas
Distribution: Slackware64 14.2
Posts: 3,293

Rep: Reputation: 1653Reputation: 1653Reputation: 1653Reputation: 1653Reputation: 1653Reputation: 1653Reputation: 1653Reputation: 1653Reputation: 1653Reputation: 1653Reputation: 1653
Quote:
Originally Posted by GazL View Post
If anyone can see any obvious flaws with this approach I'd be interested to know purely from an academic standpoint.
You are assuming that the library reference graph is a DAG; in other words, two libraries cannot reference each other directly or indirectly.

At least your method would eventually run out of stack space and bomb out versus spinning in place forever.
 
1 members found this post helpful.
Old 06-05-2010, 07:07 PM   #4
GazL
LQ Guru
 
Registered: May 2008
Posts: 5,022
Blog Entries: 16

Rep: Reputation: 2623Reputation: 2623Reputation: 2623Reputation: 2623Reputation: 2623Reputation: 2623Reputation: 2623Reputation: 2623Reputation: 2623Reputation: 2623Reputation: 2623
I started wondering how inefficient all those additional ldd runs would be because this code would re-check dependencies on libraries that had already been checked. The answer is 'very'. The following modification drops the run time down from 38 seconds to a little over 1 second!

Code:
#!/bin/bash

function already_checked()
{
        grep -q -e "^${1}$" "$CHECKED_FILE"
}

function rfind_libs()
{
        file="$1"
        echo "$file" >> "$CHECKED_FILE"
        depends="$( ldd "$file" | awk '/=. \// { print $3 }' )"
        if [ -n "$depends" ] ; then
                echo "$depends" | tr " " "\n" 
                for file in $depends
                do
                        if ! already_checked "$file" ; then
                                rfind_libs "$file"
                        fi
                done
        fi
}


CHECKED_FILE="/tmp/checked"
SOURCE_TREE="/bin"
LIB_LIST="/tmp/lib.list"

rm "$LIB_LIST" "$CHECKED_FILE" >/dev/null 2>&1
touch "$CHECKED_FILE"

while read file
do
        rfind_libs "$file" >> $LIB_LIST
done < <( find "$SOURCE_TREE" -type f )

sort -u $LIB_LIST > $LIB_LIST.sorted && mv $LIB_LIST.sorted $LIB_LIST

Last edited by GazL; 06-05-2010 at 07:33 PM.
 
Old 06-05-2010, 07:14 PM   #5
GazL
LQ Guru
 
Registered: May 2008
Posts: 5,022
Blog Entries: 16

Rep: Reputation: 2623Reputation: 2623Reputation: 2623Reputation: 2623Reputation: 2623Reputation: 2623Reputation: 2623Reputation: 2623Reputation: 2623Reputation: 2623Reputation: 2623
Quote:
Originally Posted by Richard Cranium View Post
You are assuming that the library reference graph is a DAG; in other words, two libraries cannot reference each other directly or indirectly.

At least your method would eventually run out of stack space and bomb out versus spinning in place forever.
I did consider circular dependencies as an issue, but I figured that they were unlikely to occur (how would they have been built in the first place if they both depend on each other?). Hopefully my above modification which I did for efficiency purposes would also cater for this unlikely situation but I'll have to read that page in a little more detail (maybe in the morning when I'm not as tired).

Thanks for the reply and the link Richard. I'm always keen to improve my coding skills.
 
Old 06-05-2010, 07:39 PM   #6
Richard Cranium
Senior Member
 
Registered: Apr 2009
Location: Carrollton, Texas
Distribution: Slackware64 14.2
Posts: 3,293

Rep: Reputation: 1653Reputation: 1653Reputation: 1653Reputation: 1653Reputation: 1653Reputation: 1653Reputation: 1653Reputation: 1653Reputation: 1653Reputation: 1653Reputation: 1653
Quote:
Originally Posted by GazL View Post
I did consider circular dependencies as an issue, but I figured that they were unlikely to occur (how would they have been built in the first place if they both depend on each other?).
Iteratively. Build liba.1 which doesn't need libb. Build libb.1 which needs liba.1. Now that you have libb.1, build liba.2 that now needs libb.1 but provides the same interfaces that liba.1 did.

Now having written that, I'll mention I think anyone who knowingly codes that cr*p should be taken out and beaten. A code pattern like that indicates that there is some common component that should be extracted into its own library for the other two to use.

People being people, it's possible to just miss the circular dependency. Even so, you can just not re-visit nodes in your dependency graph. Which I now see that you've done. :-D
 
2 members found this post helpful.
Old 06-05-2010, 07:51 PM   #7
bgeddy
Senior Member
 
Registered: Sep 2006
Location: Liverpool - England
Distribution: slackware64 13.37 and -current, Dragonfly BSD
Posts: 1,810

Rep: Reputation: 231Reputation: 231Reputation: 231
Quote:
You are assuming that the library reference graph is a DAG; in other words, two libraries cannot reference each other directly or indirectly.
Ah - so that's an offical term for a none cyclic relationship. I have come across these often in relational theory and other fields in IT but wasn't aware of this terminology - graphs in general are not an expert subject of mine. Thanks very much for this information.
 
Old 06-05-2010, 07:57 PM   #8
GazL
LQ Guru
 
Registered: May 2008
Posts: 5,022
Blog Entries: 16

Rep: Reputation: 2623Reputation: 2623Reputation: 2623Reputation: 2623Reputation: 2623Reputation: 2623Reputation: 2623Reputation: 2623Reputation: 2623Reputation: 2623Reputation: 2623
Thanks Richard. I understand now, and yes, most definitely beaten!
 
Old 06-05-2010, 08:02 PM   #9
Richard Cranium
Senior Member
 
Registered: Apr 2009
Location: Carrollton, Texas
Distribution: Slackware64 14.2
Posts: 3,293

Rep: Reputation: 1653Reputation: 1653Reputation: 1653Reputation: 1653Reputation: 1653Reputation: 1653Reputation: 1653Reputation: 1653Reputation: 1653Reputation: 1653Reputation: 1653
Quote:
Originally Posted by GazL View Post
Thanks Richard. I understand now, and yes, most definitely beaten!
Oh, I didn't mean your code. That was directed at the folks who wrote libraries that refer to each other. :-)
 
Old 06-05-2010, 08:06 PM   #10
Richard Cranium
Senior Member
 
Registered: Apr 2009
Location: Carrollton, Texas
Distribution: Slackware64 14.2
Posts: 3,293

Rep: Reputation: 1653Reputation: 1653Reputation: 1653Reputation: 1653Reputation: 1653Reputation: 1653Reputation: 1653Reputation: 1653Reputation: 1653Reputation: 1653Reputation: 1653
Quote:
Originally Posted by bgeddy View Post
Ah - so that's an offical term for a none cyclic relationship. I have come across these often in relational theory and other fields in IT but wasn't aware of this terminology - graphs in general are not an expert subject of mine. Thanks very much for this information.
Well, when you read up on topological sorting and stuff like that, DAGs come up. "Make" and similar tools (such as SCons or ant) need to do topological sorting of the work units (or do the functional equivalent) in order for your compiles to work. :-)
 
Old 06-05-2010, 09:26 PM   #11
Luiz Ramos
LQ Newbie
 
Registered: Jun 2010
Location: São Paulo - Brazil
Distribution: Slackware, Debian
Posts: 19

Original Poster
Rep: Reputation: 1
Hello, GazL,

Quote:
Originally Posted by GazL View Post
Interesting find Luiz, thanks for providing your
fix, and welcome to LQ.
Very happy somebody paid attention to my post... thanks a lot!

Quote:
If anyone can see any obvious flaws with this approach I'd be interested to know purely from an academic standpoint.
I don't checked your code very deeply, and I understand you are far wiser than me regarding algorithms. Only a shell trick: wouldn't be
safer to define "$file" as local in rfind_libs()?

Thanks,

Luiz
 
Old 06-06-2010, 06:49 PM   #12
GazL
LQ Guru
 
Registered: May 2008
Posts: 5,022
Blog Entries: 16

Rep: Reputation: 2623Reputation: 2623Reputation: 2623Reputation: 2623Reputation: 2623Reputation: 2623Reputation: 2623Reputation: 2623Reputation: 2623Reputation: 2623Reputation: 2623
Quote:
Originally Posted by Luiz Ramos View Post
Only a shell trick: wouldn't be
safer to define "$file" as local in rfind_libs()?
I decided not to define them as local in this case as the variables are always set right before they're used in each recursion and aren't referenced again after that.

I figured that reusing global variables rather than having each invocation have it's own set of local variables might reduce the memory footprint in the case of a deep recursion and be slightly more efficient. In practice I doubt that it'd ever get deep enough to become a problem though.

You're right though. defining them with local scope is the cleaner approach and is generally considered good practice.
 
  


Reply


Thread Tools Search this Thread
Search this Thread:

Advanced Search

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off



Similar Threads
Thread Thread Starter Forum Replies Last Post
sudo mkinitrd -o /boot/initrd.img-2.6.32.9 2.6.32.9 sudo: mkinitrd: command not foun vishwas181 Linux - Newbie 1 02-27-2010 01:16 AM
mkinitrd trouble, can't mount /dev/sda9 on /mnt bioe007 Slackware 5 07-05-2007 10:57 AM
Trouble compiling kernel, mkinitrd step shrndegruv Linux - Software 3 01-23-2005 12:57 AM
Trouble getting https going in Slack 9.1 Gates1026 Slackware 12 03-05-2004 09:34 PM
Trouble with Slack 9.0 friendoofop Slackware 1 09-19-2003 05:37 PM

LinuxQuestions.org > Forums > Linux Forums > Linux - Distributions > Slackware

All times are GMT -5. The time now is 07:23 AM.

Main Menu
Advertisement
My LQ
Write for LQ
LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
Facebook: linuxquestions Google+: linuxquestions
Open Source Consulting | Domain Registration