Lines Matching full:1
34 relatively cheap and can be very granular. Erasing however (setting bits to 1),
46 1. **Power-loss resilience** - On these systems, power can be lost at any time.
51 1. **Wear leveling** - Writing to flash is destructive. If a filesystem
56 1. **Bounded RAM/ROM** - If the above requirements weren't enough, these
75 1. First we have the non-resilient, block based filesystems, such as [FAT] and
135 1. _O(n²)_ runtime
242 complexity is _O(1)_ by bounding the input.
324 metadata pair pointer: {block 0, block 1}
330 | | |block 0 | |block 1 | |
337 block 1 is |----------------|----------------|
357 1. If our block is not full and the program size is small enough to let us
366 | revision 1 | revision 0 | => | revision 1 | revision 0 |
390 | revision 1 | revision 0 | => | revision 1 | revision 0 |
426 | revision 1 | revision 0 | => | revision 1 | revision 2 |
461 | revision 1 | revision 2 | => | revision 3 | revision 2 |
477 | revision 1 | revision 0 |
499 1. Log is empty, garbage collection occurs once every _n_ updates
512 ![cost = n + n (s / d+1)][metadata-formula1]
519 ![d = (1 - r) (size/n)][metadata-formula3]
524 ![cost = n + n (r (size/n) / ((1-r) (size/n) + 1))][metadata-formula4]
538 giving us an amortized runtime complexity of _O(1)_.
550 metadata pairs will only be 1/2 full. If we include the overhead of the second
590 | data 0 |->| data 1 |->| data 2 |->| data 4 |->| data 5 |->| data 6 |
606 | data 0 |<-| data 1 |<-| data 2 |<-| data 4 |<-| data 5 |<-| data 6 |
624 _n_-2‍_ˣ_. This means that each block contains anywhere from 1 to
630 that block contains ctz(_n_)+1 pointers.
635 | data 0 |<-| data 1 |<-| data 2 |<-| data 3 |<-| data 4 |<-| data 5 |
644 Consider a path from data block 5 to data block 1. You can see how data block 3
648 | data 0 | | data 1 |<-| data 2 | | data 3 | | data 4 |<-| data 5 |
657 | data 0 | | data 1 | | data 2 | | data 3 | | data 4 |<-| data 5 |
672 of _O(1)_, and can be read with a worst case runtime of _O(n log n)_. Given
689 ![lim,n->inf((1/n)sum,i,0->n(ctz(i)+1)) = sum,i,0->inf(1/2^i) = 2][ctz-formula1]
702 1. 32-bit CTZ skip-list => minimum block size of 104 bytes
722 ![N = sum,i,0->n(B-(w/8)(ctz(i)+1))][ctz-formula3]
729 this equation to a _O(1)_ form. While browsing the amazing resource that is
737 ![sum,i,0->n(ctz(i)+1) = 2n-popcount(n)][ctz-formula4]
741 1. ctz(![x]) = the number of trailing bits that are 0 in ![x]
742 2. popcount(![x]) = the number of bits that are 1 in ![x]
771 Now we can find both our block index and offset from a size in _O(1)_, letting
775 _O(n)_, can be appended in _O(1)_, and can be read in _O(n log n)_. All of
789 | data 0 |<-| data 1 |<-| data 2 |<-| data 3 |
804 | data 0 |<-| data 1 |<-| data 2 |<-| data 3 |
825 | data 0 |<-| data 1 |<-| data 2 |<-| data 3 | |
912 1 0 1 1 1 0 0 1 0 1 0 0
968 1. Detection and recovery from bad blocks
1225 1. [Dynamic wear leveling][wikipedia-dynamic-wear-leveling], where we
1328 | data 0 |<-| data 1 |<-| data 2 |<-| data 3 |
1426 have a ~4x storage cost, so if our file is smaller than 1/4 the block size,
1470 Once the file exceeds 1/4 the block size, we switch to a CTZ skip-list. This
2147 …1]: https://latex.codecogs.com/svg.latex?cost%20%3D%20n%20+%20n%20%5Cfrac%7Bs%7D%7Bd+1%7D
2150 …20+%20n%20%5Cfrac%7Br%5Cfrac%7Bsize%7D%7Bn%7D%7D%7B%281-r%29%5Cfrac%7Bsize%7D%7Bn%7D+1%7D
2152 …7D%7Bn%7D%5Csum_%7Bi%3D0%7D%5E%7Bn%7D%5Cleft%28%5Ctext%7Bctz%7D%28i%29+1%5Cright%29%20%3D%20%…
2154 …%5En%5Cleft%5BB-%5Cfrac%7Bw%7D%7B8%7D%5Cleft%28%5Ctext%7Bctz%7D%28i%29+1%5Cright%29%5Cright%5D
2155 …x.codecogs.com/svg.latex?%5Csum_i%5En%5Cleft%28%5Ctext%7Bctz%7D%28i%29+1%5Cright%29%20%3D%202…
2157 …%5Ctext%7Bpopcount%7D%5Cleft%28%5Cfrac%7BN%7D%7BB-2%5Cfrac%7Bw%7D%7B8%7D%7D-1%5Cright%29+2%5C…