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@+ dup 1 and if drop exit then ( adr' c )
+ >r c@+ 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@+ ( adr -- c adr' ) dup c@ swap ca1+ ;
: w@+ ( adr -- w adr' ) dup w@ swap wa1+ ;
: l@+ ( 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@+ ( hash adr' )
- w@+ ( 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@+ over cur-pino ! ( hash pino adr' )
- l@+ 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@+ ?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@+ over cur-pino ! ( pino adr' )
+ l@+ 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@+ 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@+ swap ?dup if ( adr' w )
+ dup c@ dup 1 and if ( adr b )
+ 2/ /l* dirent-offset +! ( adr )
+ ca1+ ( adr' )
+ w@+ swap ?dup if ( adr' w )
/l* dirent-offset +! ( adr' )
else ( adr' )
l@+ swap cur-pino ! ( adr' )
l@+ 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 ( )
;
