[OpenBIOS] r400 - ofw/fs/jffs2
svn at openbios.org
svn at openbios.org
Sat May 19 01:49:47 CEST 2007
Author: wmb
Date: 2007-05-19 01:49:47 +0200 (Sat, 19 May 2007)
New Revision: 400
Modified:
ofw/fs/jffs2/jffs2.fth
Log:
JFFS2 - checkpoint of new low-RAM-use version - reduces node map
RAM usage by a factor of 8 or more in pathological cases.
Modified: ofw/fs/jffs2/jffs2.fth
===================================================================
--- ofw/fs/jffs2/jffs2.fth 2007-05-18 02:48:44 UTC (rev 399)
+++ ofw/fs/jffs2/jffs2.fth 2007-05-18 23:49:47 UTC (rev 400)
@@ -7,7 +7,7 @@
0 instance value block-buf \ Start address of working buffer
0 instance value eb-end \ End address of working buffer
-\ 0 value cleanmark?
+0 value cleanmark?
\ Magic numbers to identify JFFS2 nodes
h# 1985 constant jffs2-magic
@@ -24,13 +24,17 @@
0 ( instance ) value alloc-len \ (Computed) size of inode and dirent buffers
0 ( instance ) value inodes \ Buffer for in-memory inodes
-0 ( instance ) value next-inode \ Pointer into inode buffer
+variable 'next-inode \ Pointer into inode buffer
+: next-inode ( -- val ) 'next-inode @ ;
0 ( instance ) value dirents \ Buffer for dirent nodes
-0 ( instance ) value next-dirent \ Pointer into dirent buffer
+variable 'next-dirent \ Pointer into dirent buffer
+: next-dirent ( -- val ) 'next-dirent @ ;
-0 ( instance ) value minodes \ Buffer for per-file inode list
-0 ( instance ) value next-minode \ Pointer into per-file inode list
+\ 0 ( instance ) value minodes \ Buffer for per-file inode list
+variable 'next-minode \ Pointer into per-file inode list
+: next-minode 'next-minode @ ;
+: minodes next-inode ; \ Start the inode pointer list after the inodes
0 instance value file-buf \ Buffer for constructing file
0 instance value file-size \ Actual size of file
@@ -42,6 +46,9 @@
0 ( instance ) value pages/eblock \ pages per erase block
0 ( instance ) value pages/chip \ total number of pages
+0 instance value the-page#
+0 instance value the-eblock#
+
\ In-memory inode structure
\ Access a field within a JFFS2 FLASH data structure
@@ -57,11 +64,18 @@
\ Storing it in this form saves space and time, because we only have
\ to read the full inodes for the few files that we actually access.
-: meblock@ ( adr -- eblock# ) 0 j@ ;
-: minum@ ( adr -- inode# ) 1 j@ ;
-: mversion@ ( adr -- version ) 2 j@ ;
-: moffset@ ( adr -- offset ) 3 j@ ;
-4 /l* constant /mem-inode
+instance variable splices 0 splices !
+
+: pack-offset ( offset block -- n ) the-eblock# /eblock * + ;
+
+: minum@ ( adr -- inode# ) 0 j@ ;
+: mversion@ ( adr -- version ) 1 j@ ;
+: moffset@ ( adr -- block+offset ) 2 j@ ;
+\ : moffset/block@ ( adr -- offset block ) moffset@ /eblock /mod ;
+\ : meblock@ ( adr -- eblock# ) 0 j@ ;
+\ : moffset@ ( adr -- offset ) 3 j@ ;
+\ 4 /l* constant /mem-inode
+3 /l* constant /mem-inode
\ : mtotlen@ ( adr -- offset ) 4 j@ ;
\ 5 /l* constant /mem-inode
@@ -126,7 +140,7 @@
: allocate-buffers ( -- )
/eblock dma-alloc to block-buf
/page d# 1024 max /eblock min to /empty-scan
- max-inodes /n* dma-alloc to minodes \ Arbitrary limit on inodes per file
+\ max-inodes /n* dma-alloc to minodes \ Arbitrary limit on inodes per file
first-time? if
jffs2-dirent-base to dirents
@@ -142,7 +156,7 @@
\ inodes alloc-len dma-free
\ dirents alloc-len dma-free
- minodes max-inodes /n* dma-free
+\ minodes max-inodes /n* dma-free
block-buf /eblock dma-free
@@ -212,22 +226,204 @@
drop false
;
+3 /n* instance buffer: curinum \ cur-inum, cur-vers, cur-offset
+: curvers curinum na1+ ;
+: curoffs curinum 2 na+ ;
+
+\ 0 instance variable cur-inum
+\ 0 instance variable cur-vers
+\ 0 instance variable cur-offset
+
+: init-curvars ( -- ) curinum 3 /n* erase ;
+
+1 [if]
+code aencode-inode ( version inum offset 'curinum 'next-inode -- )
+ dx pop \ dx: 'next-inode
+ cx pop \ cx: 'curinum
+ bx pop \ bx: offset
+ \ 0 [sp]: inum 4 [sp]: version
+ \ 0 [cx]: curinum 4 [cx]: curvers 8 [cx]: curoffs
+ 8 [cx] ax mov \ ax: Old curoffs
+ bx 8 [cx] mov \ Update curoffs
+ ax bx sub \ Delta
+
+ h# 200 # bx cmp < if
+ \ All 1-byte forms require offset < 200
+
+ 4 [sp] ax mov ax dec 4 [cx] ax cmp = if \ version == curvers+1 ?
+ 0 [sp] ax mov 0 [cx] ax cmp = if \ inum == curinum ?
+ 1 # bx shr \ Shift delta to remove low 0 bit
+ 0 [dx] ax mov bl 0 [ax] mov 0 [dx] inc \ Store encoded byte at next-inode++
+ 4 [cx] inc \ Update curvers
+ ax pop ax pop \ Remove inum and version from stack
+ next
+ then
+ then
+
+ 1 # 4 [sp] cmp = if \ version == 1 ?
+ 0 [sp] ax mov ax dec 0 [cx] ax cmp = if \ inum == curinum+1 ?
+ 1 # bx shr bx inc \ Shift delta and add in the next-inum bit
+ 0 [dx] ax mov bl 0 [ax] mov 0 [dx] inc \ Store encoded byte at next-inode++
+ 0 [cx] inc 1 # 4 [cx] mov \ Update inum and set curvers to p
+ ax pop ax pop \ Remove inum and version from stack
+ next
+ then
+ then
+ then
+
+ di bx mov \ Save DI in bx; we are through with the delta value
+ 0 [dx] di mov \ Get pointer in di
+ ax ax xor
+ al stosb \ encode a 0 byte to indicate the long form
+
+ ax pop \ inum
+ ax stos \ encode it
+ ax 0 [cx] mov \ Update curinum
+
+ ax pop \ version
+ ax stos \ encode it
+ ax 4 [cx] mov \ Update curvers
+
+ 8 [cx] ax mov \ offset (from already-updated curoffs)
+ ax stos \ encode it
+
+ di 0 [dx] mov \ Update next-inode
+ bx di mov \ Restore DI
+c;
+
+code amatch-inode ( inum adr endadr 'curinum -- inum false | inum adr' offset version true )
+ dx pop cx pop ax pop 0 [sp] bx mov \ dx: 'curinum cx: endadr ax: adr bx: inum
+ si push
+ ax si mov \ si: adr
+
+ begin cx si cmp u< while
+ ax ax xor
+ al lodsb \ ax: byte
+ h# 20 # al cmp u< if
+ ax lods ax 0 [dx] mov
+ ax lods ax 4 [dx] mov
+ ax lods ax 8 [dx] mov
+ else
+ 1 # al test 0<> if
+ 0 [dx] inc
+ 1 # 4 [dx] mov
+ h# fe # al and
+ else
+ 4 [dx] inc
+ then
+ ax ax add
+ ax 8 [dx] add
+ then
+ bx 0 [dx] cmp = if
+ si ax mov si pop ax push 8 [dx] push 4 [dx] push -1 # push next
+ then
+ repeat
+ si pop 0 # push
+c;
+
+[else]
+
+: short-encode ( version inum lowbit offset -- )
+ 2/ or next-inode c! 1 'next-inode +! ( inum version )
+ curinum ! curvers ! ( )
+;
+
+: encode-inode ( version inum offset -- )
+ curoffs ( version inum offset &curoffset )
+ 2dup @ - >r ( version inum offset &curoffset r: delta )
+ ! ( version inum r: delta )
+ r@ h# 200 < if ( version inum r: delta )
+ \ All 1-byte forms require offset < 200
+
+ \ 1-byte form 0: nnnnnnn0: inum = cur-inum, vers = cur-vers + 1
+ \ This is the next data node in a sequence from one file
+
+ dup curinum @ = if ( version inum )
+ over 1- curvers @ = if ( version inum )
+ 0 r> short-encode exit
+ then ( version inum )
+ then ( version inum )
+
+ \ 1-byte form 1: nnnnnnn1: inum = cur-inum + 1, vers = 1
+ \ This is the beginning of a new file
+ \ With: 4,350,592 Without: 4,476,904
+
+ dup 1- curinum @ = if ( version inum )
+ over 1 = if ( version inum )
+ 1 r> short-encode exit
+ then ( version inum )
+ then ( version inum )
+ then ( version inum r: delta )
+ r> drop ( version inum )
+
+ curinum ! curvers ! ( )
+
+ \ If we can't use a short form, use the long form:
+ \ 0.byte, inum.long, version.long, offset.long
+
+ \ At some point we might want to have another form with .short fields
+
+ next-inode
+ 0 over c! 1+ ( adr' )
+ curinum @ over ! na1+ ( adr' )
+ curvers @ over ! na1+ ( adr' )
+ curoffs @ over ! na1+ ( adr' )
+ 'next-inode ! ( )
+;
+
+: decode-inode ( adr -- len )
+ dup c@ h# 20 < if ( adr )
+ 1+
+ dup @ curinum ! na1+ ( adr' ) \ Inum
+ dup @ curvers ! na1+ ( adr' ) \ Version
+ @ curoffs ! ( ) \ Offset
+ d# 13 ( len )
+ else ( adr )
+ c@ dup 1 and if ( byte )
+ 1 curinum +! ( byte ) \ Inum
+ 1 curvers ! ( byte ) \ Version
+ 1 invert and ( byte' )
+ else ( byte )
+ 1 curvers +! ( byte ) \ Version
+ then ( byte )
+ 2* curoffs +! ( ) \ Offset
+ 1 ( len )
+ then ( len )
+;
+
+: match-inode ( inum mem-inode -- inum false | inum mem-inode' offset version true )
+ next-inode swap ?do ( inum )
+ i decode-inode ( inum len )
+ over curinum @ = if ( inum len ) \ Inum
+ i + curoffs @ curvers @ ( inum mem-inode' offset version )
+ true unloop exit
+ then ( inum len )
+ +loop ( inum )
+ false
+;
+[then]
+
\ Tools for copying into memory
: c+! ( adr c -- adr' ) over c! ca1+ ;
: l+! ( adr l -- adr' ) over l! la1+ ;
-0 instance value the-page#
-0 instance value the-eblock#
+: store-inode ( inum version offset -- )
+ -rot swap next-inode ( offset version inum adr )
+ tuck l! la1+ ( offset version adr' )
+ tuck l! la1+ ( offset adr' )
+ tuck l! la1+ ( adr' )
+ 'next-inode !
+;
\ Copy summary inode from FLASH to memory
\ Summary inode: w.nodetype l.inode l.version l.offset l.totlen
: scan-sum-inode ( adr -- len )
wa1+ \ Skip the nodetype so we can use j@
- next-inode ( adr iadr )
- the-eblock# l+! ( adr iadr' ) \ eblock@
- 2dup 3 /l* move ( adr iadr )
- 3 la+ to next-inode ( adr )
- drop d# 18
+ >r r@ 1 j@ r@ 0 j@ r> 2 j@ pack-offset ( version inum offset )
+\ store-inode
+\ encode-inode
+ curinum 'next-inode aencode-inode
+ d# 18 ( len )
;
\ Copy summary dirent from FLASH to memory
@@ -242,7 +438,7 @@
dup >r ( src dst len r: len )
move ( )
- r@ la1+ next-dirent + to next-dirent ( offset-adr )
+ r@ la1+ 'next-dirent +! ( offset-adr )
\ 6 is the length of the fields that were skipped, not copied
r> 6 + ( len )
@@ -351,21 +547,18 @@
2 pick rdnsize@ move ( adr )
dup rdnsize@ d# 22 + ( adr dirent-len )
- next-dirent + to next-dirent ( adr )
+ 'next-dirent +! ( adr )
;
\ Copy the raw inode information to memory in summary inode form
\ We do this to save space, because we will only need the full
\ information for those few inodes that correspond to the files
\ we actually access.
-: scan-raw-inode ( adr -- adr )
- next-inode ( adr iadr )
- the-eblock# l+! ( adr dadr' ) \ eblock
- over riinode@ l+! ( adr dadr' ) \ ino
- over riversion@ l+! ( adr dadr' ) \ version
- over block-buf - l+! ( adr dadr' ) \ offset
-\ over riisize@ l+! ( adr dadr' ) \ node length
- to next-inode
+: scan-raw-inode ( adr -- )
+ >r r@ riversion@ r@ riinode@ r> block-buf - pack-offset ( version inum offset )
+\ store-inode
+\ encode-inode
+ curinum 'next-inode aencode-inode
\ false to cleanmark?
;
: scan-node ( adr -- adr' )
@@ -382,7 +575,7 @@
inode-type of ( adr )
debug-scan? if ." i" then
- scan-raw-inode ( adr )
+ dup scan-raw-inode ( adr )
endof ( adr nodetype )
padding-type of ( adr )
@@ -417,8 +610,9 @@
: scan-occupied ( -- )
first-time? 0= if exit then
- dirents to next-dirent
- inodes to next-inode
+ init-curvars
+ dirents 'next-dirent !
+ inodes 'next-inode !
pages/chip 0 do
i page>eblock to the-eblock#
i no-summary? if
@@ -501,16 +695,6 @@
;
[then]
-: place-node ( node where -- )
- !
- next-minode na1+ to next-minode ( )
-;
-
-: get-inode ( mem-inode -- adr )
- dup meblock@ read-eblock
- moffset@ block-buf + ( inode-adr )
-;
-
: inode-good? ( inode -- flag )
dup d# 15 /l* crc ( riadr node-crc )
over rincrc@ <> if ( riadr )
@@ -519,95 +703,102 @@
dup >ridata over ricsize@ ( riadr data-adr data-len )
crc swap ridcrc@ =
;
-: minode-good? ( minode -- flag ) get-inode inode-good? ;
+: get-inode ( offset -- adr ) /eblock /mod read-eblock block-buf + ;
+
\ This is a brute-force, no tricks, insertion sort.
\ Insertion sort is bad for large numbers of elements, but in this
\ application, the number of elements is not all that large. The time
\ is dominated by the need to scan all the nodes. collect-nodes takes
\ about 160 ms for a tiny file (4 nodes), about 200 ms for a very large
\ one (573 nodes).
-: insert-sort ( node -- )
- dup mversion@ ( node version )
- next-minode minodes ?do ( node version )
- dup i @ mversion@ = if ( node version )
+: insert-node ( offset version adr -- )
+ \ XXX check for list overflow here
+ >r
+ r@ r@ 2 na+ next-minode r@ - move ( offset version r: adr )
+ r> 2!
+ 2 /n* 'next-minode +! ( )
+;
+
+: insert-sort ( offset version -- )
+ \ If the list is empty, insert at the beginning
+ next-minode minodes = if ( offset version )
+ minodes insert-node ( )
+ exit
+ then
+
+ \ Run the loop backwards because versions are more likely to increase
+ minodes next-minode 8 - do ( offset version )
+ dup i @ > if ( offset version )
+ \ Slide everything above up to open a slot
+ i 2 na+ insert-node ( )
+ unloop exit
+ then ( offset version )
+
+ dup i @ = if ( offset version )
\ If we have a collision, we check the CRC of the new node,
\ and if it is valid, replace the existing one. We will
\ end up with only the last good one in the slot.
- drop ( node )
- dup minode-good? if ( node )
- i ! ( )
- else ( node )
- drop ( )
- then ( )
+ drop ( offset )
+ dup get-inode inode-good? if ( offset )
+ i na1+ ! ( )
+ else ( offset )
+ drop ( )
+ then ( )
unloop exit
then
- ( node version )
- dup i @ mversion@ < if ( node version )
- \ Slide everything above up to open a slot
- i i na1+ next-minode i - move ( node version )
- drop i place-node ( node version )
- unloop exit
- then ( node version )
- /n +loop ( node version )
- drop next-minode place-node ( )
+ ( offset version )
+ -8 +loop ( offset version )
+
+ \ If we get here, the new node goes at the beginning of the list
+ minodes insert-node ( )
;
+
+\ Also used by insert-dirent
+: place-node ( node where -- )
+ !
+ /n 'next-minode +! ( )
+;
+
\ This is used for symlinks and directory inodes where there
\ can only be one of them.
--1 value max-version \ Local variable for find-node and $find-name
--1 value the-inode \ Local variable for find-node
-: latest-node ( inum -- true | minode false )
+-1 value max-version \ Local variable for latest-node and $find-name
+\ -1 value the-inode \ Local variable for latest-node
+-1 value the-offset \ Local variable for latest-node
+: latest-node ( inum -- true | offset false )
+ init-curvars
-1 to max-version
- \ Quick hack to shorten the inner loop - start at the minum field
- \ Reduces the time for a typical run from 260 ms down to 160 ms
- next-inode inodes la1+ ?do ( inum )
- dup i @ = if ( inum )
- i /l - minode-good? if ( inum )
- i /l - mversion@ ( inum version )
- dup max-version > if ( inum version )
- to max-version ( inum )
- i /l - to the-inode ( inum )
- else ( inum version )
- drop ( inum )
- then ( inum )
- then ( inum )
- then ( inum )
- /mem-inode +loop ( inum )
+ inodes begin next-inode curinum amatch-inode while ( inum inode' offset version )
+\ inodes begin match-inode while ( inum inode' offset version )
+ over get-inode inode-good? if ( inum inode' offset version )
+ dup max-version > if ( inum inode' offset version )
+ to max-version ( inum inode' offset )
+ to the-offset ( inum inode' )
+ else ( inum inode' )
+ 2drop ( inum inode' )
+ then ( inum inode' )
+ else ( inum inode' offset version )
+ 2drop ( inum inode' )
+ then ( inum inode' )
+ repeat ( inum )
drop
max-version -1 = if true exit then
- the-inode false
+ the-offset false
;
-\ This could be optimized out the wazoo, but in this application,
-\ it just doesn't matter. We only need to load one or two files.
: collect-nodes ( inum -- any? )
- minodes to next-minode \ Empty the list
+ init-curvars
+ minodes 'next-minode ! \ Empty the list
- \ Quick hack to shorten the inner loop - start at the minum field
- \ Reduces the time for a typical run from 260 ms down to 160 ms
- next-inode inodes la1+ ?do ( inum )
- dup i @ = if i /l - insert-sort then ( inum )
- /mem-inode +loop ( inum )
- drop
+ inodes begin next-inode curinum amatch-inode while ( inum inode' offset version )
+\ inodes begin match-inode while ( inum inode' offset version )
+ insert-sort ( inum inode' )
+ repeat ( inum )
+ drop ( )
next-minode minodes <>
;
-0 [if]
-\ Excessive optimization - this knocks another 70 msecs off the time
-\ The next step would be to have a word that scans to find the next one.
-code dupi@= ( n -- n flag )
- 0 [sp] cx mov \ N in ax
- 0 [bp] bx mov
- 4 [bp] bx add \ i in bx
- 0 [bx] bx mov \ i @ in bx
- ax ax xor
- bx cx cmp \ flag
- 0= if ax dec then
- ax push
-c;
-[then]
-
: set-length ( final-size write-extent -- )
2dup > if \ The final size extends past this segment
@@ -675,11 +866,7 @@
." comp " ricompr@ 3 u.r
cr
;
-: play-inode ( mem-inode -- )
- debug-scan? if
- dup meblock@ 4 u.r dup moffset@ 6 u.r space
- then
- get-inode ( inode )
+: (play-inode) ( inode -- )
dup inode-good? 0= if ( inode )
debug-scan? if ." Skipping bad inode." cr then
drop exit
@@ -705,7 +892,7 @@
-1 to the-eblock#
-1 to have-eblock#
0 to file-size
- next-minode minodes ?do i @ play-inode /n +loop
+ next-minode minodes ?do i na1+ @ get-inode (play-inode) 8 +loop
release-inflater
;
@@ -788,18 +975,14 @@
d# 1024 constant /symlink \ Max length of a symbolic link
\ The input dirent is for a symlink. Resolve it to a new dirent
-: minode>rinode ( minode -- rinode )
- dup meblock@ read-eblock ( minode )
- moffset@ block-buf + ( rinode )
-;
: dir-link ( dirent -- true | dirent' false )
delimiter >r [char] / to delimiter
/symlink alloc-mem >r
- dirino@ latest-node if ( )
+ dirino@ latest-node if ( )
true
- else ( minode )
- minode>rinode ( rinode )
+ else ( offset )
+ get-inode ( rinode )
dup >ridata swap ridsize@ ( adr len )
tuck r@ swap move ( len )
r@ swap pwd $resolve-path ( true | dirent false )
@@ -844,7 +1027,7 @@
;
: advance-dirent ( dirent -- false | dirent' true )
- pwd dirino@ swap ( parent-inode dirent )
+ pwd dirino@ swap ( parent-inode dirent )
begin dup next-dirent u< while ( par dirent )
2dup pino@ = if ( par dirent )
nip true exit
@@ -877,7 +1060,7 @@
na1+ ( minode' )
else ( minode )
\ Deleted, remove from list
- next-minode -1 na+ to next-minode ( minode )
+ -1 /n* 'next-minode +! ( minode )
dup na1+ over ( minode src dst )
next-minode over - move ( minode )
then ( minode' )
@@ -885,7 +1068,7 @@
drop ( )
;
: prep-dirents ( -- )
- minodes to next-minode \ Empty the list
+ minodes 'next-minode ! \ Empty the list
dirents
begin advance-dirent while
dup insert-dirent
@@ -894,25 +1077,6 @@
remove-unlinks
;
-0 [if]
-struct jffs2_raw_dirent
-{
-0 jint16_t magic;
-0+w jint16_t nodetype; /* == JFFS2_NODETYPE_DIRENT */
-1 jint32_t totlen;
-2 jint32_t hdr_crc;
-3 jint32_t pino;
-4 jint32_t version;
-5 jint32_t ino; /* == zero for unlink */
-6 jint32_t mctime;
-7 uint8_t nsize;
-7+b uint8_t type;
-7+w uint8_t unused[2];
-8 jint32_t node_crc;
-9 jint32_t name_crc;
-10 uint8_t name[0];
-[then]
-
\ For now, just 0 the modify time, since we only support deleting
: now-seconds ( -- secs ) 0 ;
@@ -1091,8 +1255,8 @@
0 0 0 0 0 0 ( id' s m h d m y r: dirent )
0 ( ... len r: dirent )
0 ( ... attributes r: dirent )
- else ( id' minode r: dirent )
- minode>rinode >r ( id' r: dirent rinode )
+ else ( id' offset r: dirent )
+ get-inode >r ( id' r: dirent rinode )
r@ rimtime@ sec>time&date ( id' s m h d m y r: dirent rinode )
r@ riisize@ ( id' s m h d m y len r: dirent rinode )
r> rimode@ ( id' s m h d m y len mode r: dirent )
@@ -1133,8 +1297,7 @@
: .inode ( adr )
dup minum@ 8 u.r \ Inode
dup mversion@ 8 u.r \ Version
- dup meblock@ 7 u.r \ Eblock#
- dup moffset@ 6 u.r \ Offset on eblock
+ dup moffset@ /eblock /mod 7 u.r 6 u.r \ Eblock#, offset on eblock
\ dup mtotlen@ 8 u.r \ Total length
mcr
/mem-inode +
@@ -1183,19 +1346,6 @@
-0 [if]
-// Values of type field (byte at offset h# 1d) in directory entry
-#define DT_UNKNOWN 0
-#define DT_FIFO 1
-#define DT_CHR 2
-#define DT_DIR 4
-#define DT_BLK 6
-#define DT_REG 8
-#define DT_LNK 10
-#define DT_SOCK 12
-#define DT_WHT 14
-[then]
-
\ LICENSE_BEGIN
\ Copyright (c) 2006 FirmWorks
\
More information about the OpenBIOS
mailing list