[OpenBIOS] r674 - cpu/x86/pc/olpc ofw/fs/jffs2

svn at openbios.org svn at openbios.org
Fri Oct 12 02:04:03 CEST 2007


Author: wmb
Date: 2007-10-12 02:04:02 +0200 (Fri, 12 Oct 2007)
New Revision: 674

Modified:
   cpu/x86/pc/olpc/addrs.fth
   ofw/fs/jffs2/jffs2.fth
Log:
Workaround for OLPC trac 4184 - Increase the size of the JFFS2 dirent buffer,
shrink the footprint of entries in that buffer, and do not store dirents
that obsolete the immediately-preceding one, all with the goal of surviving
"millions of dirents" JFFS2 filesystem pathologies.


Modified: cpu/x86/pc/olpc/addrs.fth
===================================================================
--- cpu/x86/pc/olpc/addrs.fth	2007-10-11 22:15:10 UTC (rev 673)
+++ cpu/x86/pc/olpc/addrs.fth	2007-10-12 00:04:02 UTC (rev 674)
@@ -74,9 +74,9 @@
 h#  20.0000 constant heap-size
 
 h# 300.0000 constant jffs2-dirent-base
-h# 400.0000 constant jffs2-inode-base
-h# 600.0000 constant dma-base
-h# a00.0000 constant dma-size
+h# 500.0000 constant jffs2-inode-base
+h# 700.0000 constant dma-base
+h# 900.0000 constant dma-size
 
 h# f.0000 constant suspend-base      \ In the DOS hole
 h# f.0008 constant resume-entry

Modified: ofw/fs/jffs2/jffs2.fth
===================================================================
--- ofw/fs/jffs2/jffs2.fth	2007-10-11 22:15:10 UTC (rev 673)
+++ ofw/fs/jffs2/jffs2.fth	2007-10-12 00:04:02 UTC (rev 674)
@@ -414,56 +414,117 @@
    d# 18                         ( len )
 ;
 
-: encode-dirent  ( boffset pino adr len -- )
-   2 pick >r                          ( boffset pino adr len r: pino )
-   crctab -rot  ($crc)                ( boffset hash )
-   next-dirent !                      ( boffset )
+\ There are three dirent record formats:
+\ delta is  current-dirent-offset - last-dirent-offset
+\ 1-byte format:  (delta >> 1) | 1                \ for delta < 0x200
+\ 2-byte format:  (delta >> 1) | 0, (delta >> 9)  \ for delta < 0x20000
+\ 10-byte format: 0.w, pino.l, offset.l   \ For delta >= 0x20000 or different pino
+\
+\ The reason for this complexity is to save space in the dirent map in the
+\ face of JFFS2 pathologies that could cause the dirent map to overflow.
+\ An example would be a filesystem with millions of hard links to the same file.
 
-   pack-offset                        ( offset )
+: +dirent  ( adr -- adr' )
+   c at +  dup 1 and  if  drop exit  then   ( adr' c )
+   >r c at + r> swap bwjoin                 ( adr' w )
+   0=  if  2 na+  then
+;
 
-   dup dirent-offset @ -  2 rshift    ( offset delta )
-   dup h# 10000 <                     ( offset delta short-offset? )
-   r@ cur-pino @ =  and               ( offset delta short-encode? )
+: #dirents  ( -- n )
+   0
+   next-dirent dirents   ( n endadr adr )
+   begin  2dup >  while   +dirent  rot 1+ -rot  repeat  ( n endadr adr )
+   2drop
+;
 
-   if                                 ( offset delta )
-      next-dirent na1+ w!             ( offset )
-      6                               ( offset de-len )
-   else                               ( offset )
-      drop  0 next-dirent na1+ w!     ( offset )
-      r@   next-dirent 6 + !          ( offset )  \ Encode pino
-      dup  next-dirent d# 10 + !      ( offset )  \ Encode offset
-      d# 14                           ( offset de-len )
-   then                               ( offset r: pino )
-   r> cur-pino !                      ( offset de-len )
-   'next-dirent +!                    ( offset )
-   dirent-offset !                    ( )
+\ ?erase-previous is an optimization/workaround for a JFFS2 pathology
+\ in which multiple nearly-identical dirents appears one after another.
+\ The pathology is caused by a garbage collection bug; we don't
+\ know if the situation can also appear for other reasons.
+\ The optimization overwrites the previous dirent record if the next
+\ one supersedes it, thus preventing the dirent buffer from filling up
+\ with millions (literally) of obsolete records.
+
+variable prev-dirent  -1 prev-dirent !  \ Needed for erasing old one
+variable prev-offset  -1 prev-offset !  \ Needed for restoring old state for regenerating
+d# 256 instance buffer: prev-name
+
+: ?erase-previous   ( boffset pino adr len -- boffset pino )
+   2dup  prev-name count  $=  0=   if   ( boffset pino adr len )
+      d# 255 min prev-name place        ( boffset pino )
+      exit
+   then                                 ( boffset pino adr len )
+   2drop                                         ( boffset pino )
+
+   dup  cur-pino @  <>  if  exit  then           ( boffset pino )
+   prev-dirent @ 'next-dirent !
+   prev-offset @ dirent-offset !
 ;
 
+: encode-dirent-long   ( offset pino -- offset dirent-len )
+   0 next-dirent w!          ( offset pino)
+   next-dirent wa1+ !        ( offset )
+   dup next-dirent 6 + !     ( offset )
+   d# 10                     ( offset dirent-len )
+;
+
+: encode-dirent  ( boffset pino adr len -- )
+   ?erase-previous                     ( boffset pino )
+
+   next-dirent d# 10 +  jffs2-inode-base  >  if
+      ." JFFS2 dirent overflow - " #dirents .d ." dirents" cr
+      abort
+   then
+
+   swap pack-offset  swap               ( offset pino )
+   dup cur-pino @ <>  if                ( offset pino )
+      dup cur-pino !                    ( offset pino )
+      encode-dirent-long                ( offset dirent-len )
+   else                                 ( offset pino )
+      over dirent-offset @ -  1 rshift  ( offset pino delta )
+      dup h# 10000 >=   if              ( offset pino delta )
+         drop encode-dirent-long        ( offset dirent-len )
+      else                              ( offset pino delta )
+         dup h# 100 <  if               ( offset pino delta )
+            1 or  next-dirent c!        ( offset pino )
+            drop  1                     ( offset dirent-len )
+         else                           ( offset pino delta )
+            next-dirent le-w!           ( offset pino )
+            drop  2                     ( offset dirent-len )
+         then
+      then                              ( offset dirent-len )
+   then                                 ( offset dirent-len )
+   next-dirent prev-dirent !            ( offset dirent-len )
+   'next-dirent +!                      ( offset )
+   dirent-offset @ prev-offset !        ( offset )
+   dirent-offset !                      ( )
+;
+
+: c at +  ( adr -- c adr' )  dup c@ swap ca1+  ;
 : w at +  ( adr -- w adr' )  dup w@ swap wa1+  ;
 : l at +  ( adr -- l adr' )  dup l@ swap la1+  ;
 
-: decode-dirent  ( adr -- false | adr' offset pino hash true )
+: decode-dirent  ( adr -- false | adr' offset pino true )
    dup  next-dirent  >=  if  drop false exit  then
-   l at +                          ( hash adr' )
-   w at +                          ( hash w adr' )
-   swap  ?dup  if               ( hash adr' w )   \ Short form
-\      swap -rot                 ( adr' hash w )
-\      /l* dirent-offset +!      ( adr' hash )
-
-      /l* dirent-offset +!      ( hash adr' )
-      swap                      ( adr' hash )
-
-      dirent-offset @           ( adr' hash offset )
-      cur-pino @ rot            ( adr' offset pino hash )
-   else                         ( hash adr' )     \ Long form
-      l at + over cur-pino !       ( hash pino adr' )
-      l at + over dirent-offset !  ( hash pino offset adr' )
-      swap 2swap swap           ( adr' offset pino hash )
-   then
+   dup c@  dup 1 and  if           ( adr c )   \ 1-byte form
+      2/  /l* dirent-offset +!     ( adr )
+      ca1+                         ( adr' )
+      dirent-offset @              ( adr offset )
+      cur-pino @                   ( adr offset pino )
+   else                            ( adr c )   \ Longer form
+      w at +  ?dup  if                ( adr' w )   \ 2-byte form
+         /w* dirent-offset +!      ( adr )
+         dirent-offset @           ( adr offset )
+         cur-pino @                ( adr offset pino )
+      else                         ( adr )     \ Long form
+         l at + over cur-pino !       ( pino adr' )
+         l at + over dirent-offset !  ( pino offset adr' )
+         swap rot                  ( adr offset pino )
+      then                         ( adr offset pino )
+   then                            ( adr offset pino )
    true
 ;
 
-
 \ Information that we need about the working file/directory
 \ The working file changes at each level of a path search
 
@@ -472,7 +533,7 @@
 0 instance value wf-type  \ Type - 4 for directory, d# 10 for symlink, etc
 
 1 [if]
-code (next-pino-match)  ( adr next-dirent pino cur-pino dirent-offset -- false | adr' offset hash true )
+code (next-pino-match)  ( adr next-dirent pino cur-pino dirent-offset -- false | adr' offset true )
    dx pop             \ dx: dirent-offset
    cx pop             \ cx: cur-pino
    bx pop             \ bx: pino
@@ -489,37 +550,51 @@
 
    \ If the first encoded dirent is short-form, the pino is the same as
    \ before and thus matches.
-   ax ax xor  op: 4 [si]  ax  mov   \ ax: w
-   ax ax or  0<>  if                \ Short form
+   ax ax xor  0 [si] al mov         \ ax: b
+   ax shr  carry?  if               \ 1-byte form
       2 # ax shl  ax 0 [dx] add     \ Update dirent-offset
-      0 [si]  cx  mov               \ cx: hash
-      6 #     si  add               \ skip long hash and word offset
+      1 #     si  add               \ skip byte offset
       4 [sp]  si  xchg              \ Put adr back on stack and restore si
       0 [dx]  bp  mov               \ bp: offset
       0 [sp]  bp  xchg              \ Put offset on stack and restore bp
-      cx          push              \ Put hash on stack
       -1 #        push              \ Put true on stack
       next
    then
 
+   op: 0 [si] ax mov                \ ax: w
+   ax ax and  0<>  if               \ 2-byte form
+      2 # ax shl  ax 0 [dx] add     \ Update dirent-offset
+      2 #     si  add               \ skip word offset
+      4 [sp]  si  xchg              \ Put adr back on stack and restore si
+      0 [dx]  bp  mov               \ bp: offset
+      0 [sp]  bp  xchg              \ Put offset on stack and restore bp
+      -1 #        push              \ Put true on stack
+      next
+   then
+
+
    long-offsets on
    begin  
-      ax ax xor  op: 4 [si]  ax  mov   \ ax: w
-      ax ax or  0<>  if                \ Short form
+      ax ax xor  0 [si] al mov         \ ax: b
+      ax shr  carry?  if               \ 1-byte form
          2 # ax shl  ax 0 [dx] add     \ Update dirent-offset
-         6 #     si  add               \ skip long hash and word offset
+         1 #     si  add               \ skip byte offset
       else
-         d# 10 [si]  ax  mov   ax  0 [dx]  mov  \ Update dirent-offset
-         d#  6 [si]  ax  mov   ax  0 [cx]  mov  \ Update cur-pino
-         d# 14 #     si  add                    \ skip record
-         ax bx cmp  =  if
-            d# -14 [si]  cx  mov       \ cx: hash
-            4 [sp]  si  xchg           \ Put adr back on stack and restore si
-            0 [dx]  bp  mov            \ bp: offset
-            0 [sp]  bp  xchg           \ Put offset on stack and restore bp
-            cx          push           \ Put hash on stack
-            -1 #        push           \ Put true on stack
-            next
+         op: 0 [si]  ax  mov           \ ax: w
+         ax ax or  0<>  if                \ Short form
+            2 # ax shl  ax 0 [dx] add     \ Update dirent-offset
+            2 #     si  add               \ skip word offset
+         else
+            d#  6 [si]  ax  mov   ax  0 [dx]  mov  \ Update dirent-offset
+            d#  2 [si]  ax  mov   ax  0 [cx]  mov  \ Update cur-pino
+            d# 10 #     si  add                    \ skip record
+            ax bx cmp  =  if
+               4 [sp]  si  xchg           \ Put adr back on stack and restore si
+               0 [dx]  bp  mov            \ bp: offset
+               0 [sp]  bp  xchg           \ Put offset on stack and restore bp
+               -1 #        push           \ Put true on stack
+               next
+            then
          then
       then
    bp si cmp  = until
@@ -530,35 +605,46 @@
    4 #     sp  add          \ clean stack
    ax ax xor  0 # 0 [sp] mov  \ return false
 c;
-: next-pino-match  ( adr -- false | pino adr' offset hash true )
+: next-pino-match  ( adr -- false | pino adr' offset true )
    next-dirent wd-inum cur-pino dirent-offset (next-pino-match)
 ;
 [then]
 
 [ifndef] next-pino-match
-: next-pino-match  ( adr -- false | adr' offset hash true )
+: next-pino-match  ( adr -- false | adr' offset true )
    dup  next-dirent  >=  if  drop false exit  then
 
    \ If the first encoded dirent is short-form, the pino is the same as
    \ before and thus matches.
-   dup la1+ w@  ?dup  if      ( adr w )
+   dup c@  dup  1 and  if     ( adr b )
+      2/ /l* dirent-offset +! ( adr )
+      dirent-offset @         ( adr offset )
+      swap  ca1+  swap        ( adr' offset )
+      true                    ( adr offset true )
+      exit
+   then                       ( adr b )
+   drop                       ( adr )
+
+   dup w@  ?dup  if           ( adr w )
       /l* dirent-offset +!    ( adr )
       dirent-offset @         ( adr offset )
-      swap  l at +  wa1+         ( offset hash adr' )
-      -rot true               ( offset hash adr' )
+      swap  wa1+  swap        ( adr' offset )
+      true                    ( adr offset true )
       exit
    then                       ( adr )
 
    begin                             ( adr )
-      la1+ w at + swap ?dup  if         ( adr' w )
+      dup c@  dup 1 and  if          ( adr b )
+         2/ /l* dirent-offset +!     ( adr )
+         ca1+                        ( adr' )
+      w at + swap ?dup  if              ( adr' w )
          /l* dirent-offset +!        ( adr' )
       else                           ( adr' )
          l at + swap cur-pino !         ( adr' )
          l at + swap dirent-offset !    ( adr' )
          wd-inum cur-pino @ =  if    ( adr' )
             dirent-offset @          ( adr' offset )
-            over -3 la+ -1 wa+ l@    ( adr' offset hash )
-            true                     ( adr' offset hash true )
+            true                     ( adr' offset true )
             exit
          then                        ( adr )
       then                           ( adr )
@@ -575,7 +661,7 @@
    r@ 1 j@  r@ 2 j@            ( offset pino )
    r@ d# 22 +  r> 5 la+ c@     ( offset pino adr namelen )
    dup >r  encode-dirent       ( r: namelen )
-   r> d# 24 +                     ( len )
+   r> d# 24 +                  ( len )
 ;
 
 [ifdef] notdef
@@ -595,6 +681,7 @@
       xattr-type  of  drop  d# 18   ( ." XA" cr )  endof
       xref-type   of  drop  6       ( ." R" cr  )  endof
       h# ffff     of  drop  dup  ( find-nonblank  )  endof  \ Keep scanning to end
+      debug-me
       ." Unrecognized summary node type " dup .x cr  abort
    endcase
 ;
@@ -1042,15 +1129,6 @@
    then
 ;
 
-: +dirent  ( adr -- adr' )   na1+ dup w@  0=  if 2 na+ then  wa1+  ;
-
-: #dirents  ( -- n )
-   0
-   next-dirent dirents   ( n endadr adr )
-   begin  2dup >  while   +dirent  rot 1+ -rot  repeat  ( n endadr adr )
-   2drop
-;
-
 char \ instance value delimiter
 
 defer $resolve-path
@@ -1083,19 +1161,13 @@
 
 : $find-name  ( name$ -- error? )
    -1 to my-vers                         ( name$ )
-   wd-inum crctab  2over  ($crc) >r      ( name$  r: hash )
 
    0 dirent-offset !
-   dirents  begin  next-pino-match  while  ( name$  adr' offset hash )
-      \ Check for a hash match
-      r@ =  if                           ( name$ adr offset )
-         2over  ?update-dirent           ( name$ adr )
-      else                               ( name$ adr  offset )
-         drop                            ( name$ adr )
-      then                               ( name$ adr )
-   repeat                                ( name$ r: hash )
-   2drop r> drop                         ( )
-   my-vers 0<   if  true exit  then      ( )
+   dirents  begin  next-pino-match  while  ( name$  adr' offset )
+      2over  ?update-dirent                ( name$ adr )
+   repeat                                  ( name$ )
+   2drop                                   ( )
+   my-vers 0<   if  true exit  then        ( )
    wf-type 4  =  if  wf-inum to wd-inum  then
    false
 ;
@@ -1209,8 +1281,8 @@
 : prep-dirents  ( -- )
    minodes 'next-minode !   \ Empty the list
    dirents                         ( adr )
-   begin  next-pino-match  while   ( adr'  offset hash )
-      drop insert-dirent           ( adr )
+   begin  next-pino-match  while   ( adr'  offset )
+      insert-dirent                ( adr )
    repeat                          ( )
 ;
 




More information about the OpenBIOS mailing list