From 74baf758e5465bb0675fb7a8e134e29467cfa7b9 Mon Sep 17 00:00:00 2001 From: Ralph Ronnquist Date: Fri, 12 Aug 2022 08:56:31 +1000 Subject: [PATCH] rework of overlay, region={beg,end} --- fusefile.c | 199 +++++++++++++++++++++++++++++++---------------------- 1 file changed, 116 insertions(+), 83 deletions(-) diff --git a/fusefile.c b/fusefile.c index 30ec7fa..01f4c58 100644 --- a/fusefile.c +++ b/fusefile.c @@ -35,8 +35,8 @@ #include struct Region { - off_t pos; - size_t size; + off_t beg; + off_t end; }; struct Source { @@ -72,18 +72,18 @@ static struct { static void usage(); -#define FRAG(m) (overlay.table+m) -#define BEG(m) (FRAG(m)->pos) -#define END(m) (FRAG(m)->pos + FRAG(m)->size) - +/** + * Find the nearest overlay.table region below pos. Returns the index, + * or -1 if there is none, i.e. pos < overlay.table[0]. + */ static ssize_t overlay_prior_fragment(off_t pos) { size_t lo = 0, hi = overlay.count; while ( lo < hi ) { size_t m = ( lo + hi ) / 2; if ( m == lo ) { - return BEG( m ) < pos? m : -1; + return overlay.table[m].beg <= pos? m : -1; } - if ( BEG( m ) <= pos ) { + if ( overlay.table[m].beg <= pos ) { lo = m; } else { hi = m; @@ -92,6 +92,11 @@ static ssize_t overlay_prior_fragment(off_t pos) { return -1; } +/** + * Save the entry count for overlay.table as 64-bit integer + * immediately following the overlay content at the index + * corresponding to the fused file size. + */ static void overlay_save_count() { lseek( overlay.source.fd, overlay.source.to, SEEK_SET ); size_t size = sizeof( overlay.count ); @@ -111,8 +116,13 @@ static void overlay_save_count() { } } +/** + * Update the on-disk cache of overlay.table between the given + * indexes. The table is laid out immediately following the table + * count with each region saved as two 64-bit unsigned integers. + */ static void overlay_save_table(size_t lo,size_t hi) { - char *p = (char *) FRAG(lo); + char *p = (char *) &overlay.table[ lo ]; size_t pos = overlay.source.to + sizeof( overlay.count ) + lo * sizeof( struct Region ); size_t size = ( hi - lo ) * sizeof( struct Region ); @@ -135,8 +145,13 @@ static void overlay_save_table(size_t lo,size_t hi) { } } -static void overlay_insert(size_t p,off_t pos,size_t size) { +/** + * Insert a new region at index p, with previous portion [p,count] + * moved up to make space. + */ +static void overlay_insert(size_t p,off_t beg,off_t end) { size_t bytes; + // Grow the table if needed if ( overlay.count >= overlay.limit ) { overlay.limit = overlay.count + 10; bytes = overlay.limit * sizeof( struct Region ); @@ -145,84 +160,111 @@ static void overlay_insert(size_t p,off_t pos,size_t size) { } bytes = ( overlay.count++ - p ) * sizeof( struct Region ); if ( bytes ) { - memmove( FRAG( p+1 ), FRAG( p ), bytes ); + memmove( (char*) &overlay.table[ p+1 ], + (char*) &overlay.table[ p ], + bytes ); } - FRAG( p )->pos = pos; - FRAG( p )->size = size; + overlay.table[ p ].beg = beg; + overlay.table[ p ].end = end; overlay_save_count(); } +/** + * Delete the region entry at p by moving the portion [p+1,count] + * down. + */ static void overlay_delete(size_t p) { - if ( p < --overlay.count ) { - size_t size = ( overlay.count - p ) * sizeof( struct Region ); - memmove( FRAG(p), FRAG(p+1), size ); + size_t bytes = ( --overlay.count - p ) * sizeof( struct Region ); + if ( bytes ) { + memmove( (char*) &overlay.table[ p ], + (char*) &overlay.table[ p+1 ], + bytes ); } - overlay_save_count(); } -static void overlay_mark(off_t pos,size_t size) { +/** + * Mark the given region as updated, i.e. written to the overlay. The + * mark region may attach to prior marked regions ro be a new, + * separate region. If attaching, it causes the prior regions to + * expand and the table adjusted by deleting any regions that become + * fully contained in other regions. + */ +static void overlay_mark(off_t beg,off_t end) { #if DEBUG - fprintf( stderr, "overlay_mark( %ld, %ld )\n", pos, size ); + fprintf( stderr, "overlay_mark( %ld, %ld )\n", beg, end ); #endif int deleted = 0; ssize_t q; - ssize_t p = overlay_prior_fragment( pos ); - // p is the nearest region below pos (or -1) - if ( p >= 0 && pos <= END(p) ) { + ssize_t p = overlay_prior_fragment( beg ); + // p is the nearest region below or at beg (or -1) + if ( p >= 0 && beg <= overlay.table[p].end ) { // p overlaps mark region - if ( END(p) >= pos + size ) { + if ( end <= overlay.table[p].end ) { + // region p covers mark region already #if DEBUG - fprintf( stderr, "overlay size 1( %ld )\n", FRAG(p)->size ); + fprintf( stderr, "overlay covering ( %ld %ld )\n", + overlay.table[p].beg, overlay.table[p].end ); #endif - return; // new mark within existing. + return; } - // new mark region extends existing - FRAG(p)->size = pos + size - BEG(p); + // the new mark region extends region p + overlay.table[p].end = end; q = p+1; - while ( q < overlay.count && BEG(q) <= END(p) ) { - if ( END(q) > END(p) ) { - FRAG(p)->size = END(q) - BEG(p); + while ( q < overlay.count && + overlay.table[q].beg <= overlay.table[p].end ) { + // Extended region merges with subsequent region + if ( overlay.table[p].end < overlay.table[q].end ) { + overlay.table[p].end = overlay.table[q].end; } overlay_delete( q ); deleted++; } - overlay_save_table( p, deleted? overlay.count : q ); + if ( deleted ) { + overlay_save_count(); + q = overlay.count; + } + overlay_save_table( p, q ); #if DEBUG - fprintf( stderr, "overlay size 2( %ld ) deleted %d\n", - FRAG(p)->size, deleted ); + fprintf( stderr, "overlay expand ( %ld %ld ) deleted %d\n", + overlay.table[p].beg, overlay.table[p].end, deleted ); #endif return; } - // The region p does not expand into new mark region - p++; // subsequent region - if ( p >= overlay.count || BEG(p) > pos + size ) { - // New mark is separate region at p - overlay_insert( p, pos, size); + // The prior region p does not expand into new mark region + p++; // subsequent region + if ( p >= overlay.count || end < overlay.table[p].beg ) { + // New mark region is a separate region at p + overlay_insert( p, beg, end ); #if DEBUG - fprintf( stderr, "overlay size 4( %ld )\n", FRAG(p)->size ); + fprintf( stderr, "overlay new ( %ld %ld )\n", + overlay.table[p].beg, overlay.table[p].end ); #endif overlay_save_table( p, overlay.count ); return; } - // New marks start before and overlap with the region - if ( BEG(p) + FRAG(p)->size < pos + size ) { - FRAG(p)->size = size; // new mark covers old region - } else { - FRAG(p)->size += BEG(p) - pos; - } - BEG(p) = pos; + // New marks start before and overlap with region p => change p + // and handle any subsequent regions being covered + overlay.table[p].beg = beg; q = p+1; - while ( q < overlay.count && BEG(q) <= END(p) ) { - if ( END(q) > END(p) ) { - FRAG(p)->size = END(q) - BEG(p); + if ( overlay.table[p].end < end ) { + overlay.table[p].end = end; + while ( q < overlay.count && + overlay.table[q].beg <= overlay.table[p].end ) { + if ( overlay.table[p].end < overlay.table[q].end ) { + overlay.table[p].end = overlay.table[q].end; + } + overlay_delete( q ); + deleted++; + } + if ( deleted ) { + overlay_save_count(); + q = overlay.count; } - overlay_delete( q ); - deleted++; } - overlay_save_table( p, deleted? overlay.count : q ); + overlay_save_table( p, q ); #if DEBUG - fprintf( stderr, "overlay size 4( %ld ) deleted %d\n", - FRAG(p)->size, deleted ); + fprintf( stderr, "overlay before ( %ld %ld ) deleted %d\n", + overlay.table[p].beg, overlay.table[p].end, deleted ); #endif } @@ -406,43 +448,34 @@ static int find_source(off_t offset) { return lo; } -static int overlay_merge(char *buf,off_t off,size_t size) { +static int overlay_merge(char *buf,off_t beg,off_t end) { #if DEBUG - fprintf( stderr, "merge %ld %ld\n", off, size ); + fprintf( stderr, "merge %ld %ld\n", beg, end ); #endif - // Find nearest overlay data before or at off - ssize_t p = overlay_prior_fragment( off ); + // Find nearest overlay data before or at beg + ssize_t p = overlay_prior_fragment( beg ); if ( p < 0 ) { p = 0; } - for ( ; p < overlay.count && BEG(p) < off+size; p++ ) { - if ( END(p) < off ) { + for ( ; p < overlay.count && overlay.table[p].beg < end; p++ ) { + if ( overlay.table[p].end < beg ) { continue; } - size_t delta = FRAG(p)->size; - if ( BEG(p) < off ) { - delta -= off - BEG(p); - } else { - size_t skip = BEG(p) - off; - off += skip; - size -= skip; - buf += skip; - } - if ( delta > size ) { - delta = size; + if ( overlay.table[p].beg > beg ) { + size_t delta = overlay.table[p].beg - beg; + buf += delta; + beg += delta; } - lseek( overlay.source.fd, off, SEEK_SET ); - while ( delta > 0 ) { - size_t n = read( overlay.source.fd, buf, delta ); - off += n; + size_t size = ( overlay.table[p].end <= end )? + ( overlay.table[p].end - beg ) : ( end - beg ); + lseek( overlay.source.fd, beg, SEEK_SET ); + while ( size > 0 ) { + size_t n = read( overlay.source.fd, buf, size ); size -= n; - delta -= n; buf += n; + beg += n; // } } -#if DEBUG - fprintf( stderr, "merged\n" ); -#endif return 0; } @@ -511,7 +544,7 @@ static int fusefile_read(const char *path, char *buf, size_t size, fsync( overlay.source.fd ); overlay.source.dirty = 0; } - int x = overlay_merge( buf + rr, off + rr, r ); + int x = overlay_merge( buf + rr, off + rr, off + rr + r ); if ( x ) { return x; } @@ -563,9 +596,9 @@ static void overlay_load() { exit( 1 ); } #if DEBUG - fprintf( stderr, "overlay region: %ld %ld\n", f.pos, f.size ); + fprintf( stderr, "overlay region: %ld %ld\n", f.beg, f.end ); #endif - overlay_mark( f.pos, f.size ); + overlay_mark( f.beg, f.end ); } } @@ -577,7 +610,7 @@ static int write_block(off_t off,const char *buf,size_t size) { fprintf( stderr, "write_block( %ld, ?, %ld )\n", off, size ); #endif if ( overlay.source.filename ) { - overlay_mark( off, size ); // Mark region as written + overlay_mark( off, off + size ); // Mark region as written } while ( size > 0 ) { int index = find_source( off ); // index of source file -- 2.39.2