Nathan Yonkee
init
Embed:
(wiki syntax)
Show/hide line numbers
lfs.c
00001 /* 00002 * The little filesystem 00003 * 00004 * Copyright (c) 2017 ARM Limited 00005 * 00006 * Licensed under the Apache License, Version 2.0 (the "License"); 00007 * you may not use this file except in compliance with the License. 00008 * You may obtain a copy of the License at 00009 * 00010 * http://www.apache.org/licenses/LICENSE-2.0 00011 * 00012 * Unless required by applicable law or agreed to in writing, software 00013 * distributed under the License is distributed on an "AS IS" BASIS, 00014 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 00015 * See the License for the specific language governing permissions and 00016 * limitations under the License. 00017 */ 00018 #include "lfs.h" 00019 #include "lfs_util.h" 00020 00021 #include <string.h> 00022 #include <stdlib.h> 00023 #include <assert.h> 00024 00025 00026 /// Caching block device operations /// 00027 static int lfs_cache_read(lfs_t *lfs, lfs_cache_t *rcache, 00028 const lfs_cache_t *pcache, lfs_block_t block, 00029 lfs_off_t off, void *buffer, lfs_size_t size) { 00030 uint8_t *data = buffer; 00031 assert(block < lfs->cfg->block_count); 00032 00033 while (size > 0) { 00034 if (pcache && block == pcache->block && off >= pcache->off && 00035 off < pcache->off + lfs->cfg->prog_size) { 00036 // is already in pcache? 00037 lfs_size_t diff = lfs_min(size, 00038 lfs->cfg->prog_size - (off-pcache->off)); 00039 memcpy(data, &pcache->buffer[off-pcache->off], diff); 00040 00041 data += diff; 00042 off += diff; 00043 size -= diff; 00044 continue; 00045 } 00046 00047 if (block == rcache->block && off >= rcache->off && 00048 off < rcache->off + lfs->cfg->read_size) { 00049 // is already in rcache? 00050 lfs_size_t diff = lfs_min(size, 00051 lfs->cfg->read_size - (off-rcache->off)); 00052 memcpy(data, &rcache->buffer[off-rcache->off], diff); 00053 00054 data += diff; 00055 off += diff; 00056 size -= diff; 00057 continue; 00058 } 00059 00060 if (off % lfs->cfg->read_size == 0 && size >= lfs->cfg->read_size) { 00061 // bypass cache? 00062 lfs_size_t diff = size - (size % lfs->cfg->read_size); 00063 int err = lfs->cfg->read(lfs->cfg, block, off, data, diff); 00064 if (err) { 00065 return err; 00066 } 00067 00068 data += diff; 00069 off += diff; 00070 size -= diff; 00071 continue; 00072 } 00073 00074 // load to cache, first condition can no longer fail 00075 rcache->block = block; 00076 rcache->off = off - (off % lfs->cfg->read_size); 00077 int err = lfs->cfg->read(lfs->cfg, rcache->block, 00078 rcache->off, rcache->buffer, lfs->cfg->read_size); 00079 if (err) { 00080 return err; 00081 } 00082 } 00083 00084 return 0; 00085 } 00086 00087 static int lfs_cache_cmp(lfs_t *lfs, lfs_cache_t *rcache, 00088 const lfs_cache_t *pcache, lfs_block_t block, 00089 lfs_off_t off, const void *buffer, lfs_size_t size) { 00090 const uint8_t *data = buffer; 00091 00092 for (lfs_off_t i = 0; i < size; i++) { 00093 uint8_t c; 00094 int err = lfs_cache_read(lfs, rcache, pcache, 00095 block, off+i, &c, 1); 00096 if (err) { 00097 return err; 00098 } 00099 00100 if (c != data[i]) { 00101 return false; 00102 } 00103 } 00104 00105 return true; 00106 } 00107 00108 static int lfs_cache_crc(lfs_t *lfs, lfs_cache_t *rcache, 00109 const lfs_cache_t *pcache, lfs_block_t block, 00110 lfs_off_t off, lfs_size_t size, uint32_t *crc) { 00111 for (lfs_off_t i = 0; i < size; i++) { 00112 uint8_t c; 00113 int err = lfs_cache_read(lfs, rcache, pcache, 00114 block, off+i, &c, 1); 00115 if (err) { 00116 return err; 00117 } 00118 00119 lfs_crc(crc, &c, 1); 00120 } 00121 00122 return 0; 00123 } 00124 00125 static int lfs_cache_flush(lfs_t *lfs, 00126 lfs_cache_t *pcache, lfs_cache_t *rcache) { 00127 if (pcache->block != 0xffffffff) { 00128 int err = lfs->cfg->prog(lfs->cfg, pcache->block, 00129 pcache->off, pcache->buffer, lfs->cfg->prog_size); 00130 if (err) { 00131 return err; 00132 } 00133 00134 if (rcache) { 00135 int res = lfs_cache_cmp(lfs, rcache, NULL, pcache->block, 00136 pcache->off, pcache->buffer, lfs->cfg->prog_size); 00137 if (res < 0) { 00138 return res; 00139 } 00140 00141 if (!res) { 00142 return LFS_ERR_CORRUPT; 00143 } 00144 } 00145 00146 pcache->block = 0xffffffff; 00147 } 00148 00149 return 0; 00150 } 00151 00152 static int lfs_cache_prog(lfs_t *lfs, lfs_cache_t *pcache, 00153 lfs_cache_t *rcache, lfs_block_t block, 00154 lfs_off_t off, const void *buffer, lfs_size_t size) { 00155 const uint8_t *data = buffer; 00156 assert(block < lfs->cfg->block_count); 00157 00158 while (size > 0) { 00159 if (block == pcache->block && off >= pcache->off && 00160 off < pcache->off + lfs->cfg->prog_size) { 00161 // is already in pcache? 00162 lfs_size_t diff = lfs_min(size, 00163 lfs->cfg->prog_size - (off-pcache->off)); 00164 memcpy(&pcache->buffer[off-pcache->off], data, diff); 00165 00166 data += diff; 00167 off += diff; 00168 size -= diff; 00169 00170 if (off % lfs->cfg->prog_size == 0) { 00171 // eagerly flush out pcache if we fill up 00172 int err = lfs_cache_flush(lfs, pcache, rcache); 00173 if (err) { 00174 return err; 00175 } 00176 } 00177 00178 continue; 00179 } 00180 00181 // pcache must have been flushed, either by programming and 00182 // entire block or manually flushing the pcache 00183 assert(pcache->block == 0xffffffff); 00184 00185 if (off % lfs->cfg->prog_size == 0 && 00186 size >= lfs->cfg->prog_size) { 00187 // bypass pcache? 00188 lfs_size_t diff = size - (size % lfs->cfg->prog_size); 00189 int err = lfs->cfg->prog(lfs->cfg, block, off, data, diff); 00190 if (err) { 00191 return err; 00192 } 00193 00194 if (rcache) { 00195 int res = lfs_cache_cmp(lfs, rcache, NULL, 00196 block, off, data, diff); 00197 if (res < 0) { 00198 return res; 00199 } 00200 00201 if (!res) { 00202 return LFS_ERR_CORRUPT; 00203 } 00204 } 00205 00206 data += diff; 00207 off += diff; 00208 size -= diff; 00209 continue; 00210 } 00211 00212 // prepare pcache, first condition can no longer fail 00213 pcache->block = block; 00214 pcache->off = off - (off % lfs->cfg->prog_size); 00215 } 00216 00217 return 0; 00218 } 00219 00220 00221 /// General lfs block device operations /// 00222 static int lfs_bd_read(lfs_t *lfs, lfs_block_t block, 00223 lfs_off_t off, void *buffer, lfs_size_t size) { 00224 // if we ever do more than writes to alternating pairs, 00225 // this may need to consider pcache 00226 return lfs_cache_read(lfs, &lfs->rcache, NULL, 00227 block, off, buffer, size); 00228 } 00229 00230 static int lfs_bd_prog(lfs_t *lfs, lfs_block_t block, 00231 lfs_off_t off, const void *buffer, lfs_size_t size) { 00232 return lfs_cache_prog(lfs, &lfs->pcache, NULL, 00233 block, off, buffer, size); 00234 } 00235 00236 static int lfs_bd_cmp(lfs_t *lfs, lfs_block_t block, 00237 lfs_off_t off, const void *buffer, lfs_size_t size) { 00238 return lfs_cache_cmp(lfs, &lfs->rcache, NULL, block, off, buffer, size); 00239 } 00240 00241 static int lfs_bd_crc(lfs_t *lfs, lfs_block_t block, 00242 lfs_off_t off, lfs_size_t size, uint32_t *crc) { 00243 return lfs_cache_crc(lfs, &lfs->rcache, NULL, block, off, size, crc); 00244 } 00245 00246 static int lfs_bd_erase(lfs_t *lfs, lfs_block_t block) { 00247 return lfs->cfg->erase(lfs->cfg, block); 00248 } 00249 00250 static int lfs_bd_sync(lfs_t *lfs) { 00251 lfs->rcache.block = 0xffffffff; 00252 00253 int err = lfs_cache_flush(lfs, &lfs->pcache, NULL); 00254 if (err) { 00255 return err; 00256 } 00257 00258 return lfs->cfg->sync(lfs->cfg); 00259 } 00260 00261 00262 /// Internal operations predeclared here /// 00263 int lfs_traverse(lfs_t *lfs, int (*cb)(void*, lfs_block_t), void *data); 00264 static int lfs_pred(lfs_t *lfs, const lfs_block_t dir[2], lfs_dir_t *pdir); 00265 static int lfs_parent(lfs_t *lfs, const lfs_block_t dir[2], 00266 lfs_dir_t *parent, lfs_entry_t *entry); 00267 static int lfs_moved(lfs_t *lfs, const void *e); 00268 static int lfs_relocate(lfs_t *lfs, 00269 const lfs_block_t oldpair[2], const lfs_block_t newpair[2]); 00270 int lfs_deorphan(lfs_t *lfs); 00271 00272 00273 /// Block allocator /// 00274 static int lfs_alloc_lookahead(void *p, lfs_block_t block) { 00275 lfs_t *lfs = p; 00276 00277 lfs_block_t off = (((lfs_soff_t)(block - lfs->free.begin) 00278 % (lfs_soff_t)(lfs->cfg->block_count)) 00279 + lfs->cfg->block_count) % lfs->cfg->block_count; 00280 00281 if (off < lfs->cfg->lookahead) { 00282 lfs->free.buffer[off / 32] |= 1U << (off % 32); 00283 } 00284 00285 return 0; 00286 } 00287 00288 static int lfs_alloc(lfs_t *lfs, lfs_block_t *block) { 00289 while (true) { 00290 while (true) { 00291 // check if we have looked at all blocks since last ack 00292 if (lfs->free.begin + lfs->free.off == lfs->free.end) { 00293 LFS_WARN("No more free space %ld", lfs->free.end); 00294 return LFS_ERR_NOSPC; 00295 } 00296 00297 if (lfs->free.off >= lfs_min( 00298 lfs->cfg->lookahead, lfs->cfg->block_count)) { 00299 break; 00300 } 00301 00302 lfs_block_t off = lfs->free.off; 00303 lfs->free.off += 1; 00304 00305 if (!(lfs->free.buffer[off / 32] & (1U << (off % 32)))) { 00306 // found a free block 00307 *block = (lfs->free.begin + off) % lfs->cfg->block_count; 00308 return 0; 00309 } 00310 } 00311 00312 lfs->free.begin += lfs_min(lfs->cfg->lookahead, lfs->cfg->block_count); 00313 lfs->free.off = 0; 00314 00315 // find mask of free blocks from tree 00316 memset(lfs->free.buffer, 0, lfs->cfg->lookahead/8); 00317 int err = lfs_traverse(lfs, lfs_alloc_lookahead, lfs); 00318 if (err) { 00319 return err; 00320 } 00321 } 00322 } 00323 00324 static void lfs_alloc_ack(lfs_t *lfs) { 00325 lfs->free.end = lfs->free.begin + lfs->free.off + lfs->cfg->block_count; 00326 } 00327 00328 00329 /// Metadata pair and directory operations /// 00330 static inline void lfs_pairswap(lfs_block_t pair[2]) { 00331 lfs_block_t t = pair[0]; 00332 pair[0] = pair[1]; 00333 pair[1] = t; 00334 } 00335 00336 static inline bool lfs_pairisnull(const lfs_block_t pair[2]) { 00337 return pair[0] == 0xffffffff || pair[1] == 0xffffffff; 00338 } 00339 00340 static inline int lfs_paircmp( 00341 const lfs_block_t paira[2], 00342 const lfs_block_t pairb[2]) { 00343 return !(paira[0] == pairb[0] || paira[1] == pairb[1] || 00344 paira[0] == pairb[1] || paira[1] == pairb[0]); 00345 } 00346 00347 static inline bool lfs_pairsync( 00348 const lfs_block_t paira[2], 00349 const lfs_block_t pairb[2]) { 00350 return (paira[0] == pairb[0] && paira[1] == pairb[1]) || 00351 (paira[0] == pairb[1] && paira[1] == pairb[0]); 00352 } 00353 00354 static inline lfs_size_t lfs_entry_size(const lfs_entry_t *entry) { 00355 return 4 + entry->d.elen + entry->d.alen + entry->d.nlen; 00356 } 00357 00358 static int lfs_dir_alloc(lfs_t *lfs, lfs_dir_t *dir) { 00359 // allocate pair of dir blocks 00360 for (int i = 0; i < 2; i++) { 00361 int err = lfs_alloc(lfs, &dir->pair[i]); 00362 if (err) { 00363 return err; 00364 } 00365 } 00366 00367 // rather than clobbering one of the blocks we just pretend 00368 // the revision may be valid 00369 int err = lfs_bd_read(lfs, dir->pair[0], 0, &dir->d.rev, 4); 00370 if (err) { 00371 return err; 00372 } 00373 00374 // set defaults 00375 dir->d.rev += 1; 00376 dir->d.size = sizeof(dir->d)+4; 00377 dir->d.tail[0] = 0xffffffff; 00378 dir->d.tail[1] = 0xffffffff; 00379 dir->off = sizeof(dir->d); 00380 00381 // don't write out yet, let caller take care of that 00382 return 0; 00383 } 00384 00385 static int lfs_dir_fetch(lfs_t *lfs, 00386 lfs_dir_t *dir, const lfs_block_t pair[2]) { 00387 // copy out pair, otherwise may be aliasing dir 00388 const lfs_block_t tpair[2] = {pair[0], pair[1]}; 00389 bool valid = false; 00390 00391 // check both blocks for the most recent revision 00392 for (int i = 0; i < 2; i++) { 00393 struct lfs_disk_dir test; 00394 int err = lfs_bd_read(lfs, tpair[i], 0, &test, sizeof(test)); 00395 if (err) { 00396 return err; 00397 } 00398 00399 if (valid && lfs_scmp(test.rev, dir->d.rev) < 0) { 00400 continue; 00401 } 00402 00403 if ((0x7fffffff & test.size) < sizeof(test)+4 || 00404 (0x7fffffff & test.size) > lfs->cfg->block_size) { 00405 continue; 00406 } 00407 00408 uint32_t crc = 0xffffffff; 00409 lfs_crc(&crc, &test, sizeof(test)); 00410 err = lfs_bd_crc(lfs, tpair[i], sizeof(test), 00411 (0x7fffffff & test.size) - sizeof(test), &crc); 00412 if (err) { 00413 return err; 00414 } 00415 00416 if (crc != 0) { 00417 continue; 00418 } 00419 00420 valid = true; 00421 00422 // setup dir in case it's valid 00423 dir->pair[0] = tpair[(i+0) % 2]; 00424 dir->pair[1] = tpair[(i+1) % 2]; 00425 dir->off = sizeof(dir->d); 00426 dir->d = test; 00427 } 00428 00429 if (!valid) { 00430 LFS_ERROR("Corrupted dir pair at %ld %ld", tpair[0], tpair[1]); 00431 return LFS_ERR_CORRUPT; 00432 } 00433 00434 return 0; 00435 } 00436 00437 struct lfs_region { 00438 lfs_off_t oldoff; 00439 lfs_size_t oldlen; 00440 const void *newdata; 00441 lfs_size_t newlen; 00442 }; 00443 00444 static int lfs_dir_commit(lfs_t *lfs, lfs_dir_t *dir, 00445 const struct lfs_region *regions, int count) { 00446 // increment revision count 00447 dir->d.rev += 1; 00448 00449 // keep pairs in order such that pair[0] is most recent 00450 lfs_pairswap(dir->pair); 00451 for (int i = 0; i < count; i++) { 00452 dir->d.size += regions[i].newlen - regions[i].oldlen; 00453 } 00454 00455 const lfs_block_t oldpair[2] = {dir->pair[0], dir->pair[1]}; 00456 bool relocated = false; 00457 00458 while (true) { 00459 if (true) { 00460 int err = lfs_bd_erase(lfs, dir->pair[0]); 00461 if (err) { 00462 if (err == LFS_ERR_CORRUPT) { 00463 goto relocate; 00464 } 00465 return err; 00466 } 00467 00468 uint32_t crc = 0xffffffff; 00469 lfs_crc(&crc, &dir->d, sizeof(dir->d)); 00470 err = lfs_bd_prog(lfs, dir->pair[0], 0, &dir->d, sizeof(dir->d)); 00471 if (err) { 00472 if (err == LFS_ERR_CORRUPT) { 00473 goto relocate; 00474 } 00475 return err; 00476 } 00477 00478 int i = 0; 00479 lfs_off_t oldoff = sizeof(dir->d); 00480 lfs_off_t newoff = sizeof(dir->d); 00481 while (newoff < (0x7fffffff & dir->d.size)-4) { 00482 if (i < count && regions[i].oldoff == oldoff) { 00483 lfs_crc(&crc, regions[i].newdata, regions[i].newlen); 00484 int err = lfs_bd_prog(lfs, dir->pair[0], 00485 newoff, regions[i].newdata, regions[i].newlen); 00486 if (err) { 00487 if (err == LFS_ERR_CORRUPT) { 00488 goto relocate; 00489 } 00490 return err; 00491 } 00492 00493 oldoff += regions[i].oldlen; 00494 newoff += regions[i].newlen; 00495 i += 1; 00496 } else { 00497 uint8_t data; 00498 int err = lfs_bd_read(lfs, oldpair[1], oldoff, &data, 1); 00499 if (err) { 00500 return err; 00501 } 00502 00503 lfs_crc(&crc, &data, 1); 00504 err = lfs_bd_prog(lfs, dir->pair[0], newoff, &data, 1); 00505 if (err) { 00506 if (err == LFS_ERR_CORRUPT) { 00507 goto relocate; 00508 } 00509 return err; 00510 } 00511 00512 oldoff += 1; 00513 newoff += 1; 00514 } 00515 } 00516 00517 err = lfs_bd_prog(lfs, dir->pair[0], newoff, &crc, 4); 00518 if (err) { 00519 if (err == LFS_ERR_CORRUPT) { 00520 goto relocate; 00521 } 00522 return err; 00523 } 00524 00525 err = lfs_bd_sync(lfs); 00526 if (err) { 00527 if (err == LFS_ERR_CORRUPT) { 00528 goto relocate; 00529 } 00530 return err; 00531 } 00532 00533 // successful commit, check checksum to make sure 00534 uint32_t ncrc = 0xffffffff; 00535 err = lfs_bd_crc(lfs, dir->pair[0], 0, 00536 (0x7fffffff & dir->d.size)-4, &ncrc); 00537 if (err) { 00538 return err; 00539 } 00540 00541 if (ncrc != crc) { 00542 goto relocate; 00543 } 00544 } 00545 00546 break; 00547 relocate: 00548 //commit was corrupted 00549 LFS_DEBUG("Bad block at %ld", dir->pair[0]); 00550 00551 // drop caches and prepare to relocate block 00552 relocated = true; 00553 lfs->pcache.block = 0xffffffff; 00554 00555 // can't relocate superblock, filesystem is now frozen 00556 if (lfs_paircmp(oldpair, (const lfs_block_t[2]){0, 1}) == 0) { 00557 LFS_WARN("Superblock %ld has become unwritable", oldpair[0]); 00558 return LFS_ERR_CORRUPT; 00559 } 00560 00561 // relocate half of pair 00562 int err = lfs_alloc(lfs, &dir->pair[0]); 00563 if (err) { 00564 return err; 00565 } 00566 } 00567 00568 if (relocated) { 00569 // update references if we relocated 00570 LFS_DEBUG("Relocating %ld %ld to %ld %ld", 00571 oldpair[0], oldpair[1], dir->pair[0], dir->pair[1]); 00572 int err = lfs_relocate(lfs, oldpair, dir->pair); 00573 if (err) { 00574 return err; 00575 } 00576 } 00577 00578 // shift over any directories that are affected 00579 for (lfs_dir_t *d = lfs->dirs; d; d = d->next) { 00580 if (lfs_paircmp(d->pair, dir->pair) == 0) { 00581 d->pair[0] = dir->pair[0]; 00582 d->pair[1] = dir->pair[1]; 00583 } 00584 } 00585 00586 return 0; 00587 } 00588 00589 static int lfs_dir_update(lfs_t *lfs, lfs_dir_t *dir, 00590 const lfs_entry_t *entry, const void *data) { 00591 return lfs_dir_commit(lfs, dir, (struct lfs_region[]){ 00592 {entry->off, sizeof(entry->d), &entry->d, sizeof(entry->d)}, 00593 {entry->off+sizeof(entry->d), entry->d.nlen, data, entry->d.nlen} 00594 }, data ? 2 : 1); 00595 } 00596 00597 static int lfs_dir_append(lfs_t *lfs, lfs_dir_t *dir, 00598 lfs_entry_t *entry, const void *data) { 00599 // check if we fit, if top bit is set we do not and move on 00600 while (true) { 00601 if (dir->d.size + lfs_entry_size(entry) <= lfs->cfg->block_size) { 00602 entry->off = dir->d.size - 4; 00603 return lfs_dir_commit(lfs, dir, (struct lfs_region[]){ 00604 {entry->off, 0, &entry->d, sizeof(entry->d)}, 00605 {entry->off, 0, data, entry->d.nlen} 00606 }, 2); 00607 } 00608 00609 // we need to allocate a new dir block 00610 if (!(0x80000000 & dir->d.size)) { 00611 lfs_dir_t newdir; 00612 int err = lfs_dir_alloc(lfs, &newdir); 00613 if (err) { 00614 return err; 00615 } 00616 00617 newdir.d.tail[0] = dir->d.tail[0]; 00618 newdir.d.tail[1] = dir->d.tail[1]; 00619 entry->off = newdir.d.size - 4; 00620 err = lfs_dir_commit(lfs, &newdir, (struct lfs_region[]){ 00621 {entry->off, 0, &entry->d, sizeof(entry->d)}, 00622 {entry->off, 0, data, entry->d.nlen} 00623 }, 2); 00624 if (err) { 00625 return err; 00626 } 00627 00628 dir->d.size |= 0x80000000; 00629 dir->d.tail[0] = newdir.pair[0]; 00630 dir->d.tail[1] = newdir.pair[1]; 00631 return lfs_dir_commit(lfs, dir, NULL, 0); 00632 } 00633 00634 int err = lfs_dir_fetch(lfs, dir, dir->d.tail); 00635 if (err) { 00636 return err; 00637 } 00638 } 00639 } 00640 00641 static int lfs_dir_remove(lfs_t *lfs, lfs_dir_t *dir, lfs_entry_t *entry) { 00642 // check if we should just drop the directory block 00643 if ((dir->d.size & 0x7fffffff) == sizeof(dir->d)+4 00644 + lfs_entry_size(entry)) { 00645 lfs_dir_t pdir; 00646 int res = lfs_pred(lfs, dir->pair, &pdir); 00647 if (res < 0) { 00648 return res; 00649 } 00650 00651 if (pdir.d.size & 0x80000000) { 00652 pdir.d.size &= dir->d.size | 0x7fffffff; 00653 pdir.d.tail[0] = dir->d.tail[0]; 00654 pdir.d.tail[1] = dir->d.tail[1]; 00655 return lfs_dir_commit(lfs, &pdir, NULL, 0); 00656 } 00657 } 00658 00659 // shift out the entry 00660 int err = lfs_dir_commit(lfs, dir, (struct lfs_region[]){ 00661 {entry->off, lfs_entry_size(entry), NULL, 0}, 00662 }, 1); 00663 if (err) { 00664 return err; 00665 } 00666 00667 // shift over any files/directories that are affected 00668 for (lfs_file_t *f = lfs->files; f; f = f->next) { 00669 if (lfs_paircmp(f->pair, dir->pair) == 0) { 00670 if (f->poff == entry->off) { 00671 f->pair[0] = 0xffffffff; 00672 f->pair[1] = 0xffffffff; 00673 } else if (f->poff > entry->off) { 00674 f->poff -= lfs_entry_size(entry); 00675 } 00676 } 00677 } 00678 00679 for (lfs_dir_t *d = lfs->dirs; d; d = d->next) { 00680 if (lfs_paircmp(d->pair, dir->pair) == 0) { 00681 if (d->off > entry->off) { 00682 d->off -= lfs_entry_size(entry); 00683 d->pos -= lfs_entry_size(entry); 00684 } 00685 } 00686 } 00687 00688 return 0; 00689 } 00690 00691 static int lfs_dir_next(lfs_t *lfs, lfs_dir_t *dir, lfs_entry_t *entry) { 00692 while (dir->off + sizeof(entry->d) > (0x7fffffff & dir->d.size)-4) { 00693 if (!(0x80000000 & dir->d.size)) { 00694 entry->off = dir->off; 00695 return LFS_ERR_NOENT; 00696 } 00697 00698 int err = lfs_dir_fetch(lfs, dir, dir->d.tail); 00699 if (err) { 00700 return err; 00701 } 00702 00703 dir->off = sizeof(dir->d); 00704 dir->pos += sizeof(dir->d) + 4; 00705 } 00706 00707 int err = lfs_bd_read(lfs, dir->pair[0], dir->off, 00708 &entry->d, sizeof(entry->d)); 00709 if (err) { 00710 return err; 00711 } 00712 00713 entry->off = dir->off; 00714 dir->off += lfs_entry_size(entry); 00715 dir->pos += lfs_entry_size(entry); 00716 return 0; 00717 } 00718 00719 static int lfs_dir_find(lfs_t *lfs, lfs_dir_t *dir, 00720 lfs_entry_t *entry, const char **path) { 00721 const char *pathname = *path; 00722 size_t pathlen; 00723 00724 while (true) { 00725 nextname: 00726 // skip slashes 00727 pathname += strspn(pathname, "/"); 00728 pathlen = strcspn(pathname, "/"); 00729 00730 // skip '.' and root '..' 00731 if ((pathlen == 1 && memcmp(pathname, ".", 1) == 0) || 00732 (pathlen == 2 && memcmp(pathname, "..", 2) == 0)) { 00733 pathname += pathlen; 00734 goto nextname; 00735 } 00736 00737 // skip if matched by '..' in name 00738 const char *suffix = pathname + pathlen; 00739 size_t sufflen; 00740 int depth = 1; 00741 while (true) { 00742 suffix += strspn(suffix, "/"); 00743 sufflen = strcspn(suffix, "/"); 00744 if (sufflen == 0) { 00745 break; 00746 } 00747 00748 if (sufflen == 2 && memcmp(suffix, "..", 2) == 0) { 00749 depth -= 1; 00750 if (depth == 0) { 00751 pathname = suffix + sufflen; 00752 goto nextname; 00753 } 00754 } else { 00755 depth += 1; 00756 } 00757 00758 suffix += sufflen; 00759 } 00760 00761 // update what we've found 00762 *path = pathname; 00763 00764 // find path 00765 while (true) { 00766 int err = lfs_dir_next(lfs, dir, entry); 00767 if (err) { 00768 return err; 00769 } 00770 00771 if (((0x7f & entry->d.type) != LFS_TYPE_REG && 00772 (0x7f & entry->d.type) != LFS_TYPE_DIR) || 00773 entry->d.nlen != pathlen) { 00774 continue; 00775 } 00776 00777 int res = lfs_bd_cmp(lfs, dir->pair[0], 00778 entry->off + 4+entry->d.elen+entry->d.alen, 00779 pathname, pathlen); 00780 if (res < 0) { 00781 return res; 00782 } 00783 00784 // found match 00785 if (res) { 00786 break; 00787 } 00788 } 00789 00790 // check that entry has not been moved 00791 if (entry->d.type & 0x80) { 00792 int moved = lfs_moved(lfs, &entry->d.u); 00793 if (moved < 0 || moved) { 00794 return (moved < 0) ? moved : LFS_ERR_NOENT; 00795 } 00796 00797 entry->d.type &= ~0x80; 00798 } 00799 00800 pathname += pathlen; 00801 pathname += strspn(pathname, "/"); 00802 if (pathname[0] == '\0') { 00803 return 0; 00804 } 00805 00806 // continue on if we hit a directory 00807 if (entry->d.type != LFS_TYPE_DIR) { 00808 return LFS_ERR_NOTDIR; 00809 } 00810 00811 int err = lfs_dir_fetch(lfs, dir, entry->d.u.dir); 00812 if (err) { 00813 return err; 00814 } 00815 } 00816 } 00817 00818 00819 /// Top level directory operations /// 00820 int lfs_mkdir(lfs_t *lfs, const char *path) { 00821 // deorphan if we haven't yet, needed at most once after poweron 00822 if (!lfs->deorphaned) { 00823 int err = lfs_deorphan(lfs); 00824 if (err) { 00825 return err; 00826 } 00827 } 00828 00829 // fetch parent directory 00830 lfs_dir_t cwd; 00831 int err = lfs_dir_fetch(lfs, &cwd, lfs->root); 00832 if (err) { 00833 return err; 00834 } 00835 00836 lfs_entry_t entry; 00837 err = lfs_dir_find(lfs, &cwd, &entry, &path); 00838 if (err != LFS_ERR_NOENT || strchr(path, '/') != NULL) { 00839 return err ? err : LFS_ERR_EXIST; 00840 } 00841 00842 // build up new directory 00843 lfs_alloc_ack(lfs); 00844 00845 lfs_dir_t dir; 00846 err = lfs_dir_alloc(lfs, &dir); 00847 if (err) { 00848 return err; 00849 } 00850 dir.d.tail[0] = cwd.d.tail[0]; 00851 dir.d.tail[1] = cwd.d.tail[1]; 00852 00853 err = lfs_dir_commit(lfs, &dir, NULL, 0); 00854 if (err) { 00855 return err; 00856 } 00857 00858 entry.d.type = LFS_TYPE_DIR; 00859 entry.d.elen = sizeof(entry.d) - 4; 00860 entry.d.alen = 0; 00861 entry.d.nlen = strlen(path); 00862 entry.d.u.dir[0] = dir.pair[0]; 00863 entry.d.u.dir[1] = dir.pair[1]; 00864 00865 cwd.d.tail[0] = dir.pair[0]; 00866 cwd.d.tail[1] = dir.pair[1]; 00867 00868 err = lfs_dir_append(lfs, &cwd, &entry, path); 00869 if (err) { 00870 return err; 00871 } 00872 00873 lfs_alloc_ack(lfs); 00874 return 0; 00875 } 00876 00877 int lfs_dir_open(lfs_t *lfs, lfs_dir_t *dir, const char *path) { 00878 dir->pair[0] = lfs->root[0]; 00879 dir->pair[1] = lfs->root[1]; 00880 00881 int err = lfs_dir_fetch(lfs, dir, dir->pair); 00882 if (err) { 00883 return err; 00884 } 00885 00886 // check for root, can only be something like '/././../.' 00887 if (strspn(path, "/.") == strlen(path)) { 00888 dir->head[0] = dir->pair[0]; 00889 dir->head[1] = dir->pair[1]; 00890 dir->pos = sizeof(dir->d) - 2; 00891 dir->off = sizeof(dir->d); 00892 return 0; 00893 } 00894 00895 lfs_entry_t entry; 00896 err = lfs_dir_find(lfs, dir, &entry, &path); 00897 if (err) { 00898 return err; 00899 } else if (entry.d.type != LFS_TYPE_DIR) { 00900 return LFS_ERR_NOTDIR; 00901 } 00902 00903 err = lfs_dir_fetch(lfs, dir, entry.d.u.dir); 00904 if (err) { 00905 return err; 00906 } 00907 00908 // setup head dir 00909 // special offset for '.' and '..' 00910 dir->head[0] = dir->pair[0]; 00911 dir->head[1] = dir->pair[1]; 00912 dir->pos = sizeof(dir->d) - 2; 00913 dir->off = sizeof(dir->d); 00914 00915 // add to list of directories 00916 dir->next = lfs->dirs; 00917 lfs->dirs = dir; 00918 00919 return 0; 00920 } 00921 00922 int lfs_dir_close(lfs_t *lfs, lfs_dir_t *dir) { 00923 // remove from list of directories 00924 for (lfs_dir_t **p = &lfs->dirs; *p; p = &(*p)->next) { 00925 if (*p == dir) { 00926 *p = dir->next; 00927 break; 00928 } 00929 } 00930 00931 return 0; 00932 } 00933 00934 int lfs_dir_read(lfs_t *lfs, lfs_dir_t *dir, struct lfs_info *info) { 00935 memset(info, 0, sizeof(*info)); 00936 00937 // special offset for '.' and '..' 00938 if (dir->pos == sizeof(dir->d) - 2) { 00939 info->type = LFS_TYPE_DIR; 00940 strcpy(info->name, "."); 00941 dir->pos += 1; 00942 return 1; 00943 } else if (dir->pos == sizeof(dir->d) - 1) { 00944 info->type = LFS_TYPE_DIR; 00945 strcpy(info->name, ".."); 00946 dir->pos += 1; 00947 return 1; 00948 } 00949 00950 lfs_entry_t entry; 00951 while (true) { 00952 int err = lfs_dir_next(lfs, dir, &entry); 00953 if (err) { 00954 return (err == LFS_ERR_NOENT) ? 0 : err; 00955 } 00956 00957 if ((0x7f & entry.d.type) != LFS_TYPE_REG && 00958 (0x7f & entry.d.type) != LFS_TYPE_DIR) { 00959 continue; 00960 } 00961 00962 // check that entry has not been moved 00963 if (entry.d.type & 0x80) { 00964 int moved = lfs_moved(lfs, &entry.d.u); 00965 if (moved < 0) { 00966 return moved; 00967 } 00968 00969 if (moved) { 00970 continue; 00971 } 00972 00973 entry.d.type &= ~0x80; 00974 } 00975 00976 break; 00977 } 00978 00979 info->type = entry.d.type; 00980 if (info->type == LFS_TYPE_REG) { 00981 info->size = entry.d.u.file.size; 00982 } 00983 00984 int err = lfs_bd_read(lfs, dir->pair[0], 00985 entry.off + 4+entry.d.elen+entry.d.alen, 00986 info->name, entry.d.nlen); 00987 if (err) { 00988 return err; 00989 } 00990 00991 return 1; 00992 } 00993 00994 int lfs_dir_seek(lfs_t *lfs, lfs_dir_t *dir, lfs_off_t off) { 00995 // simply walk from head dir 00996 int err = lfs_dir_rewind(lfs, dir); 00997 if (err) { 00998 return err; 00999 } 01000 dir->pos = off; 01001 01002 while (off > (0x7fffffff & dir->d.size)) { 01003 off -= 0x7fffffff & dir->d.size; 01004 if (!(0x80000000 & dir->d.size)) { 01005 return LFS_ERR_INVAL; 01006 } 01007 01008 int err = lfs_dir_fetch(lfs, dir, dir->d.tail); 01009 if (err) { 01010 return err; 01011 } 01012 } 01013 01014 dir->off = off; 01015 return 0; 01016 } 01017 01018 lfs_soff_t lfs_dir_tell(lfs_t *lfs, lfs_dir_t *dir) { 01019 return dir->pos; 01020 } 01021 01022 int lfs_dir_rewind(lfs_t *lfs, lfs_dir_t *dir) { 01023 // reload the head dir 01024 int err = lfs_dir_fetch(lfs, dir, dir->head); 01025 if (err) { 01026 return err; 01027 } 01028 01029 dir->pair[0] = dir->head[0]; 01030 dir->pair[1] = dir->head[1]; 01031 dir->pos = sizeof(dir->d) - 2; 01032 dir->off = sizeof(dir->d); 01033 return 0; 01034 } 01035 01036 01037 /// File index list operations /// 01038 static int lfs_ctz_index(lfs_t *lfs, lfs_off_t *off) { 01039 lfs_off_t size = *off; 01040 lfs_off_t b = lfs->cfg->block_size - 2*4; 01041 lfs_off_t i = size / b; 01042 if (i == 0) { 01043 return 0; 01044 } 01045 01046 i = (size - 4*(lfs_popc(i-1)+2)) / b; 01047 *off = size - b*i - 4*lfs_popc(i); 01048 return i; 01049 } 01050 01051 static int lfs_ctz_find(lfs_t *lfs, 01052 lfs_cache_t *rcache, const lfs_cache_t *pcache, 01053 lfs_block_t head, lfs_size_t size, 01054 lfs_size_t pos, lfs_block_t *block, lfs_off_t *off) { 01055 if (size == 0) { 01056 *block = 0xffffffff; 01057 *off = 0; 01058 return 0; 01059 } 01060 01061 lfs_off_t current = lfs_ctz_index(lfs, &(lfs_off_t){size-1}); 01062 lfs_off_t target = lfs_ctz_index(lfs, &pos); 01063 01064 while (current > target) { 01065 lfs_size_t skip = lfs_min( 01066 lfs_npw2(current-target+1) - 1, 01067 lfs_ctz(current)); 01068 01069 int err = lfs_cache_read(lfs, rcache, pcache, head, 4*skip, &head, 4); 01070 if (err) { 01071 return err; 01072 } 01073 01074 assert(head >= 2 && head <= lfs->cfg->block_count); 01075 current -= 1 << skip; 01076 } 01077 01078 *block = head; 01079 *off = pos; 01080 return 0; 01081 } 01082 01083 static int lfs_ctz_extend(lfs_t *lfs, 01084 lfs_cache_t *rcache, lfs_cache_t *pcache, 01085 lfs_block_t head, lfs_size_t size, 01086 lfs_block_t *block, lfs_off_t *off) { 01087 while (true) { 01088 // go ahead and grab a block 01089 lfs_block_t nblock; 01090 int err = lfs_alloc(lfs, &nblock); 01091 if (err) { 01092 return err; 01093 } 01094 assert(nblock >= 2 && nblock <= lfs->cfg->block_count); 01095 01096 if (true) { 01097 err = lfs_bd_erase(lfs, nblock); 01098 if (err) { 01099 if (err == LFS_ERR_CORRUPT) { 01100 goto relocate; 01101 } 01102 return err; 01103 } 01104 01105 if (size == 0) { 01106 *block = nblock; 01107 *off = 0; 01108 return 0; 01109 } 01110 01111 size -= 1; 01112 lfs_off_t index = lfs_ctz_index(lfs, &size); 01113 size += 1; 01114 01115 // just copy out the last block if it is incomplete 01116 if (size != lfs->cfg->block_size) { 01117 for (lfs_off_t i = 0; i < size; i++) { 01118 uint8_t data; 01119 int err = lfs_cache_read(lfs, rcache, NULL, 01120 head, i, &data, 1); 01121 if (err) { 01122 return err; 01123 } 01124 01125 err = lfs_cache_prog(lfs, pcache, rcache, 01126 nblock, i, &data, 1); 01127 if (err) { 01128 if (err == LFS_ERR_CORRUPT) { 01129 goto relocate; 01130 } 01131 return err; 01132 } 01133 } 01134 01135 *block = nblock; 01136 *off = size; 01137 return 0; 01138 } 01139 01140 // append block 01141 index += 1; 01142 lfs_size_t skips = lfs_ctz(index) + 1; 01143 01144 for (lfs_off_t i = 0; i < skips; i++) { 01145 int err = lfs_cache_prog(lfs, pcache, rcache, 01146 nblock, 4*i, &head, 4); 01147 if (err) { 01148 if (err == LFS_ERR_CORRUPT) { 01149 goto relocate; 01150 } 01151 return err; 01152 } 01153 01154 if (i != skips-1) { 01155 err = lfs_cache_read(lfs, rcache, NULL, 01156 head, 4*i, &head, 4); 01157 if (err) { 01158 return err; 01159 } 01160 } 01161 01162 assert(head >= 2 && head <= lfs->cfg->block_count); 01163 } 01164 01165 *block = nblock; 01166 *off = 4*skips; 01167 return 0; 01168 } 01169 01170 relocate: 01171 LFS_DEBUG("Bad block at %ld", nblock); 01172 01173 // just clear cache and try a new block 01174 pcache->block = 0xffffffff; 01175 } 01176 } 01177 01178 static int lfs_ctz_traverse(lfs_t *lfs, 01179 lfs_cache_t *rcache, const lfs_cache_t *pcache, 01180 lfs_block_t head, lfs_size_t size, 01181 int (*cb)(void*, lfs_block_t), void *data) { 01182 if (size == 0) { 01183 return 0; 01184 } 01185 01186 lfs_off_t index = lfs_ctz_index(lfs, &(lfs_off_t){size-1}); 01187 01188 while (true) { 01189 int err = cb(data, head); 01190 if (err) { 01191 return err; 01192 } 01193 01194 if (index == 0) { 01195 return 0; 01196 } 01197 01198 err = lfs_cache_read(lfs, rcache, pcache, head, 0, &head, 4); 01199 if (err) { 01200 return err; 01201 } 01202 01203 index -= 1; 01204 } 01205 } 01206 01207 01208 /// Top level file operations /// 01209 int lfs_file_open(lfs_t *lfs, lfs_file_t *file, 01210 const char *path, int flags) { 01211 // deorphan if we haven't yet, needed at most once after poweron 01212 if ((flags & 3) != LFS_O_RDONLY && !lfs->deorphaned) { 01213 int err = lfs_deorphan(lfs); 01214 if (err) { 01215 return err; 01216 } 01217 } 01218 01219 // allocate entry for file if it doesn't exist 01220 lfs_dir_t cwd; 01221 int err = lfs_dir_fetch(lfs, &cwd, lfs->root); 01222 if (err) { 01223 return err; 01224 } 01225 01226 lfs_entry_t entry; 01227 err = lfs_dir_find(lfs, &cwd, &entry, &path); 01228 if (err && (err != LFS_ERR_NOENT || strchr(path, '/') != NULL)) { 01229 return err; 01230 } 01231 01232 if (err == LFS_ERR_NOENT) { 01233 if (!(flags & LFS_O_CREAT)) { 01234 return LFS_ERR_NOENT; 01235 } 01236 01237 // create entry to remember name 01238 entry.d.type = LFS_TYPE_REG; 01239 entry.d.elen = sizeof(entry.d) - 4; 01240 entry.d.alen = 0; 01241 entry.d.nlen = strlen(path); 01242 entry.d.u.file.head = 0xffffffff; 01243 entry.d.u.file.size = 0; 01244 err = lfs_dir_append(lfs, &cwd, &entry, path); 01245 if (err) { 01246 return err; 01247 } 01248 } else if (entry.d.type == LFS_TYPE_DIR) { 01249 return LFS_ERR_ISDIR; 01250 } else if (flags & LFS_O_EXCL) { 01251 return LFS_ERR_EXIST; 01252 } 01253 01254 // setup file struct 01255 file->pair[0] = cwd.pair[0]; 01256 file->pair[1] = cwd.pair[1]; 01257 file->poff = entry.off; 01258 file->head = entry.d.u.file.head; 01259 file->size = entry.d.u.file.size; 01260 file->flags = flags; 01261 file->pos = 0; 01262 01263 if (flags & LFS_O_TRUNC) { 01264 if (file->size != 0) { 01265 file->flags |= LFS_F_DIRTY; 01266 } 01267 file->head = 0xffffffff; 01268 file->size = 0; 01269 } 01270 01271 // allocate buffer if needed 01272 file->cache.block = 0xffffffff; 01273 if (lfs->cfg->file_buffer) { 01274 file->cache.buffer = lfs->cfg->file_buffer; 01275 } else if ((file->flags & 3) == LFS_O_RDONLY) { 01276 file->cache.buffer = malloc(lfs->cfg->read_size); 01277 if (!file->cache.buffer) { 01278 return LFS_ERR_NOMEM; 01279 } 01280 } else { 01281 file->cache.buffer = malloc(lfs->cfg->prog_size); 01282 if (!file->cache.buffer) { 01283 return LFS_ERR_NOMEM; 01284 } 01285 } 01286 01287 // add to list of files 01288 file->next = lfs->files; 01289 lfs->files = file; 01290 01291 return 0; 01292 } 01293 01294 int lfs_file_close(lfs_t *lfs, lfs_file_t *file) { 01295 int err = lfs_file_sync(lfs, file); 01296 01297 // remove from list of files 01298 for (lfs_file_t **p = &lfs->files; *p; p = &(*p)->next) { 01299 if (*p == file) { 01300 *p = file->next; 01301 break; 01302 } 01303 } 01304 01305 // clean up memory 01306 if (!lfs->cfg->file_buffer) { 01307 free(file->cache.buffer); 01308 } 01309 01310 return err; 01311 } 01312 01313 static int lfs_file_relocate(lfs_t *lfs, lfs_file_t *file) { 01314 relocate: 01315 LFS_DEBUG("Bad block at %ld", file->block); 01316 01317 // just relocate what exists into new block 01318 lfs_block_t nblock; 01319 int err = lfs_alloc(lfs, &nblock); 01320 if (err) { 01321 return err; 01322 } 01323 01324 err = lfs_bd_erase(lfs, nblock); 01325 if (err) { 01326 if (err == LFS_ERR_CORRUPT) { 01327 goto relocate; 01328 } 01329 return err; 01330 } 01331 01332 // either read from dirty cache or disk 01333 for (lfs_off_t i = 0; i < file->off; i++) { 01334 uint8_t data; 01335 err = lfs_cache_read(lfs, &lfs->rcache, &file->cache, 01336 file->block, i, &data, 1); 01337 if (err) { 01338 return err; 01339 } 01340 01341 err = lfs_cache_prog(lfs, &lfs->pcache, &lfs->rcache, 01342 nblock, i, &data, 1); 01343 if (err) { 01344 if (err == LFS_ERR_CORRUPT) { 01345 goto relocate; 01346 } 01347 return err; 01348 } 01349 } 01350 01351 // copy over new state of file 01352 memcpy(file->cache.buffer, lfs->pcache.buffer, lfs->cfg->prog_size); 01353 file->cache.block = lfs->pcache.block; 01354 file->cache.off = lfs->pcache.off; 01355 lfs->pcache.block = 0xffffffff; 01356 01357 file->block = nblock; 01358 return 0; 01359 } 01360 01361 static int lfs_file_flush(lfs_t *lfs, lfs_file_t *file) { 01362 if (file->flags & LFS_F_READING) { 01363 // just drop read cache 01364 file->cache.block = 0xffffffff; 01365 file->flags &= ~LFS_F_READING; 01366 } 01367 01368 if (file->flags & LFS_F_WRITING) { 01369 lfs_off_t pos = file->pos; 01370 01371 // copy over anything after current branch 01372 lfs_file_t orig = { 01373 .head = file->head, 01374 .size = file->size, 01375 .flags = LFS_O_RDONLY, 01376 .pos = file->pos, 01377 .cache = lfs->rcache, 01378 }; 01379 lfs->rcache.block = 0xffffffff; 01380 01381 while (file->pos < file->size) { 01382 // copy over a byte at a time, leave it up to caching 01383 // to make this efficient 01384 uint8_t data; 01385 lfs_ssize_t res = lfs_file_read(lfs, &orig, &data, 1); 01386 if (res < 0) { 01387 return res; 01388 } 01389 01390 res = lfs_file_write(lfs, file, &data, 1); 01391 if (res < 0) { 01392 return res; 01393 } 01394 01395 // keep our reference to the rcache in sync 01396 if (lfs->rcache.block != 0xffffffff) { 01397 orig.cache.block = 0xffffffff; 01398 lfs->rcache.block = 0xffffffff; 01399 } 01400 } 01401 01402 // write out what we have 01403 while (true) { 01404 int err = lfs_cache_flush(lfs, &file->cache, &lfs->rcache); 01405 if (err) { 01406 if (err == LFS_ERR_CORRUPT) { 01407 goto relocate; 01408 } 01409 return err; 01410 } 01411 01412 break; 01413 relocate: 01414 err = lfs_file_relocate(lfs, file); 01415 if (err) { 01416 return err; 01417 } 01418 } 01419 01420 // actual file updates 01421 file->head = file->block; 01422 file->size = file->pos; 01423 file->flags &= ~LFS_F_WRITING; 01424 file->flags |= LFS_F_DIRTY; 01425 01426 file->pos = pos; 01427 } 01428 01429 return 0; 01430 } 01431 01432 int lfs_file_sync(lfs_t *lfs, lfs_file_t *file) { 01433 int err = lfs_file_flush(lfs, file); 01434 if (err) { 01435 return err; 01436 } 01437 01438 if ((file->flags & LFS_F_DIRTY) && 01439 !(file->flags & LFS_F_ERRED) && 01440 !lfs_pairisnull(file->pair)) { 01441 // update dir entry 01442 lfs_dir_t cwd; 01443 int err = lfs_dir_fetch(lfs, &cwd, file->pair); 01444 if (err) { 01445 return err; 01446 } 01447 01448 lfs_entry_t entry = {.off = file->poff}; 01449 err = lfs_bd_read(lfs, cwd.pair[0], entry.off, 01450 &entry.d, sizeof(entry.d)); 01451 if (err) { 01452 return err; 01453 } 01454 01455 if (entry.d.type != LFS_TYPE_REG) { 01456 // sanity check valid entry 01457 return LFS_ERR_INVAL; 01458 } 01459 01460 entry.d.u.file.head = file->head; 01461 entry.d.u.file.size = file->size; 01462 01463 err = lfs_dir_update(lfs, &cwd, &entry, NULL); 01464 if (err) { 01465 return err; 01466 } 01467 01468 file->flags &= ~LFS_F_DIRTY; 01469 } 01470 01471 return 0; 01472 } 01473 01474 lfs_ssize_t lfs_file_read(lfs_t *lfs, lfs_file_t *file, 01475 void *buffer, lfs_size_t size) { 01476 uint8_t *data = buffer; 01477 lfs_size_t nsize = size; 01478 01479 if ((file->flags & 3) == LFS_O_WRONLY) { 01480 return LFS_ERR_INVAL; 01481 } 01482 01483 if (file->flags & LFS_F_WRITING) { 01484 // flush out any writes 01485 int err = lfs_file_flush(lfs, file); 01486 if (err) { 01487 return err; 01488 } 01489 } 01490 01491 if (file->pos >= file->size) { 01492 // eof if past end 01493 return 0; 01494 } 01495 01496 size = lfs_min(size, file->size - file->pos); 01497 nsize = size; 01498 01499 while (nsize > 0) { 01500 // check if we need a new block 01501 if (!(file->flags & LFS_F_READING) || 01502 file->off == lfs->cfg->block_size) { 01503 int err = lfs_ctz_find(lfs, &file->cache, NULL, 01504 file->head, file->size, 01505 file->pos, &file->block, &file->off); 01506 if (err) { 01507 return err; 01508 } 01509 01510 file->flags |= LFS_F_READING; 01511 } 01512 01513 // read as much as we can in current block 01514 lfs_size_t diff = lfs_min(nsize, lfs->cfg->block_size - file->off); 01515 int err = lfs_cache_read(lfs, &file->cache, NULL, 01516 file->block, file->off, data, diff); 01517 if (err) { 01518 return err; 01519 } 01520 01521 file->pos += diff; 01522 file->off += diff; 01523 data += diff; 01524 nsize -= diff; 01525 } 01526 01527 return size; 01528 } 01529 01530 lfs_ssize_t lfs_file_write(lfs_t *lfs, lfs_file_t *file, 01531 const void *buffer, lfs_size_t size) { 01532 const uint8_t *data = buffer; 01533 lfs_size_t nsize = size; 01534 01535 if ((file->flags & 3) == LFS_O_RDONLY) { 01536 return LFS_ERR_INVAL; 01537 } 01538 01539 if (file->flags & LFS_F_READING) { 01540 // drop any reads 01541 int err = lfs_file_flush(lfs, file); 01542 if (err) { 01543 return err; 01544 } 01545 } 01546 01547 if ((file->flags & LFS_O_APPEND) && file->pos < file->size) { 01548 file->pos = file->size; 01549 } 01550 01551 if (!(file->flags & LFS_F_WRITING) && file->pos > file->size) { 01552 // fill with zeros 01553 lfs_off_t pos = file->pos; 01554 file->pos = file->size; 01555 01556 while (file->pos < pos) { 01557 lfs_ssize_t res = lfs_file_write(lfs, file, &(uint8_t){0}, 1); 01558 if (res < 0) { 01559 return res; 01560 } 01561 } 01562 } 01563 01564 while (nsize > 0) { 01565 // check if we need a new block 01566 if (!(file->flags & LFS_F_WRITING) || 01567 file->off == lfs->cfg->block_size) { 01568 if (!(file->flags & LFS_F_WRITING) && file->pos > 0) { 01569 // find out which block we're extending from 01570 int err = lfs_ctz_find(lfs, &file->cache, NULL, 01571 file->head, file->size, 01572 file->pos-1, &file->block, &file->off); 01573 if (err) { 01574 file->flags |= LFS_F_ERRED; 01575 return err; 01576 } 01577 01578 // mark cache as dirty since we may have read data into it 01579 file->cache.block = 0xffffffff; 01580 } 01581 01582 // extend file with new blocks 01583 lfs_alloc_ack(lfs); 01584 int err = lfs_ctz_extend(lfs, &lfs->rcache, &file->cache, 01585 file->block, file->pos, 01586 &file->block, &file->off); 01587 if (err) { 01588 file->flags |= LFS_F_ERRED; 01589 return err; 01590 } 01591 01592 file->flags |= LFS_F_WRITING; 01593 } 01594 01595 // program as much as we can in current block 01596 lfs_size_t diff = lfs_min(nsize, lfs->cfg->block_size - file->off); 01597 while (true) { 01598 int err = lfs_cache_prog(lfs, &file->cache, &lfs->rcache, 01599 file->block, file->off, data, diff); 01600 if (err) { 01601 if (err == LFS_ERR_CORRUPT) { 01602 goto relocate; 01603 } 01604 file->flags |= LFS_F_ERRED; 01605 return err; 01606 } 01607 01608 break; 01609 relocate: 01610 err = lfs_file_relocate(lfs, file); 01611 if (err) { 01612 file->flags |= LFS_F_ERRED; 01613 return err; 01614 } 01615 } 01616 01617 file->pos += diff; 01618 file->off += diff; 01619 data += diff; 01620 nsize -= diff; 01621 01622 lfs_alloc_ack(lfs); 01623 } 01624 01625 file->flags &= ~LFS_F_ERRED; 01626 return size; 01627 } 01628 01629 lfs_soff_t lfs_file_seek(lfs_t *lfs, lfs_file_t *file, 01630 lfs_soff_t off, int whence) { 01631 // write out everything beforehand, may be noop if rdonly 01632 int err = lfs_file_flush(lfs, file); 01633 if (err) { 01634 return err; 01635 } 01636 01637 // update pos 01638 if (whence == LFS_SEEK_SET) { 01639 file->pos = off; 01640 } else if (whence == LFS_SEEK_CUR) { 01641 if (off < 0 && (lfs_off_t)-off > file->pos) { 01642 return LFS_ERR_INVAL; 01643 } 01644 01645 file->pos = file->pos + off; 01646 } else if (whence == LFS_SEEK_END) { 01647 if (off < 0 && (lfs_off_t)-off > file->size) { 01648 return LFS_ERR_INVAL; 01649 } 01650 01651 file->pos = file->size + off; 01652 } 01653 01654 return file->pos; 01655 } 01656 01657 lfs_soff_t lfs_file_tell(lfs_t *lfs, lfs_file_t *file) { 01658 return file->pos; 01659 } 01660 01661 int lfs_file_rewind(lfs_t *lfs, lfs_file_t *file) { 01662 lfs_soff_t res = lfs_file_seek(lfs, file, 0, LFS_SEEK_SET); 01663 if (res < 0) { 01664 return res; 01665 } 01666 01667 return 0; 01668 } 01669 01670 lfs_soff_t lfs_file_size(lfs_t *lfs, lfs_file_t *file) { 01671 return lfs_max(file->pos, file->size); 01672 } 01673 01674 01675 /// General fs oprations /// 01676 int lfs_stat(lfs_t *lfs, const char *path, struct lfs_info *info) { 01677 // check for root, can only be something like '/././../.' 01678 if (strspn(path, "/.") == strlen(path)) { 01679 memset(info, 0, sizeof(*info)); 01680 info->type = LFS_TYPE_DIR; 01681 strcpy(info->name, "/"); 01682 return 0; 01683 } 01684 01685 lfs_dir_t cwd; 01686 int err = lfs_dir_fetch(lfs, &cwd, lfs->root); 01687 if (err) { 01688 return err; 01689 } 01690 01691 lfs_entry_t entry; 01692 err = lfs_dir_find(lfs, &cwd, &entry, &path); 01693 if (err) { 01694 return err; 01695 } 01696 01697 memset(info, 0, sizeof(*info)); 01698 info->type = entry.d.type; 01699 if (info->type == LFS_TYPE_REG) { 01700 info->size = entry.d.u.file.size; 01701 } 01702 01703 err = lfs_bd_read(lfs, cwd.pair[0], 01704 entry.off + 4+entry.d.elen+entry.d.alen, 01705 info->name, entry.d.nlen); 01706 if (err) { 01707 return err; 01708 } 01709 01710 return 0; 01711 } 01712 01713 int lfs_remove(lfs_t *lfs, const char *path) { 01714 // deorphan if we haven't yet, needed at most once after poweron 01715 if (!lfs->deorphaned) { 01716 int err = lfs_deorphan(lfs); 01717 if (err) { 01718 return err; 01719 } 01720 } 01721 01722 lfs_dir_t cwd; 01723 int err = lfs_dir_fetch(lfs, &cwd, lfs->root); 01724 if (err) { 01725 return err; 01726 } 01727 01728 lfs_entry_t entry; 01729 err = lfs_dir_find(lfs, &cwd, &entry, &path); 01730 if (err) { 01731 return err; 01732 } 01733 01734 lfs_dir_t dir; 01735 if (entry.d.type == LFS_TYPE_DIR) { 01736 // must be empty before removal, checking size 01737 // without masking top bit checks for any case where 01738 // dir is not empty 01739 int err = lfs_dir_fetch(lfs, &dir, entry.d.u.dir); 01740 if (err) { 01741 return err; 01742 } else if (dir.d.size != sizeof(dir.d)+4) { 01743 return LFS_ERR_INVAL; 01744 } 01745 } 01746 01747 // remove the entry 01748 err = lfs_dir_remove(lfs, &cwd, &entry); 01749 if (err) { 01750 return err; 01751 } 01752 01753 // if we were a directory, find pred, replace tail 01754 if (entry.d.type == LFS_TYPE_DIR) { 01755 int res = lfs_pred(lfs, dir.pair, &cwd); 01756 if (res < 0) { 01757 return res; 01758 } 01759 01760 assert(res); // must have pred 01761 cwd.d.tail[0] = dir.d.tail[0]; 01762 cwd.d.tail[1] = dir.d.tail[1]; 01763 01764 int err = lfs_dir_commit(lfs, &cwd, NULL, 0); 01765 if (err) { 01766 return err; 01767 } 01768 } 01769 01770 return 0; 01771 } 01772 01773 int lfs_rename(lfs_t *lfs, const char *oldpath, const char *newpath) { 01774 // deorphan if we haven't yet, needed at most once after poweron 01775 if (!lfs->deorphaned) { 01776 int err = lfs_deorphan(lfs); 01777 if (err) { 01778 return err; 01779 } 01780 } 01781 01782 // find old entry 01783 lfs_dir_t oldcwd; 01784 int err = lfs_dir_fetch(lfs, &oldcwd, lfs->root); 01785 if (err) { 01786 return err; 01787 } 01788 01789 lfs_entry_t oldentry; 01790 err = lfs_dir_find(lfs, &oldcwd, &oldentry, &oldpath); 01791 if (err) { 01792 return err; 01793 } 01794 01795 // allocate new entry 01796 lfs_dir_t newcwd; 01797 err = lfs_dir_fetch(lfs, &newcwd, lfs->root); 01798 if (err) { 01799 return err; 01800 } 01801 01802 lfs_entry_t preventry; 01803 err = lfs_dir_find(lfs, &newcwd, &preventry, &newpath); 01804 if (err && (err != LFS_ERR_NOENT || strchr(newpath, '/') != NULL)) { 01805 return err; 01806 } 01807 01808 bool prevexists = (err != LFS_ERR_NOENT); 01809 bool samepair = (lfs_paircmp(oldcwd.pair, newcwd.pair) == 0); 01810 01811 // must have same type 01812 if (prevexists && preventry.d.type != oldentry.d.type) { 01813 return LFS_ERR_INVAL; 01814 } 01815 01816 lfs_dir_t dir; 01817 if (prevexists && preventry.d.type == LFS_TYPE_DIR) { 01818 // must be empty before removal, checking size 01819 // without masking top bit checks for any case where 01820 // dir is not empty 01821 int err = lfs_dir_fetch(lfs, &dir, preventry.d.u.dir); 01822 if (err) { 01823 return err; 01824 } else if (dir.d.size != sizeof(dir.d)+4) { 01825 return LFS_ERR_INVAL; 01826 } 01827 } 01828 01829 // mark as moving 01830 oldentry.d.type |= 0x80; 01831 err = lfs_dir_update(lfs, &oldcwd, &oldentry, NULL); 01832 if (err) { 01833 return err; 01834 } 01835 01836 // update pair if newcwd == oldcwd 01837 if (samepair) { 01838 newcwd = oldcwd; 01839 } 01840 01841 // move to new location 01842 lfs_entry_t newentry = preventry; 01843 newentry.d = oldentry.d; 01844 newentry.d.type &= ~0x80; 01845 newentry.d.nlen = strlen(newpath); 01846 01847 if (prevexists) { 01848 int err = lfs_dir_update(lfs, &newcwd, &newentry, newpath); 01849 if (err) { 01850 return err; 01851 } 01852 } else { 01853 int err = lfs_dir_append(lfs, &newcwd, &newentry, newpath); 01854 if (err) { 01855 return err; 01856 } 01857 } 01858 01859 // update pair if newcwd == oldcwd 01860 if (samepair) { 01861 oldcwd = newcwd; 01862 } 01863 01864 // remove old entry 01865 err = lfs_dir_remove(lfs, &oldcwd, &oldentry); 01866 if (err) { 01867 return err; 01868 } 01869 01870 // if we were a directory, find pred, replace tail 01871 if (prevexists && preventry.d.type == LFS_TYPE_DIR) { 01872 int res = lfs_pred(lfs, dir.pair, &newcwd); 01873 if (res < 0) { 01874 return res; 01875 } 01876 01877 assert(res); // must have pred 01878 newcwd.d.tail[0] = dir.d.tail[0]; 01879 newcwd.d.tail[1] = dir.d.tail[1]; 01880 01881 int err = lfs_dir_commit(lfs, &newcwd, NULL, 0); 01882 if (err) { 01883 return err; 01884 } 01885 } 01886 01887 return 0; 01888 } 01889 01890 01891 /// Filesystem operations /// 01892 static int lfs_init(lfs_t *lfs, const struct lfs_config *cfg) { 01893 lfs->cfg = cfg; 01894 01895 // setup read cache 01896 lfs->rcache.block = 0xffffffff; 01897 if (lfs->cfg->read_buffer) { 01898 lfs->rcache.buffer = lfs->cfg->read_buffer; 01899 } else { 01900 lfs->rcache.buffer = malloc(lfs->cfg->read_size); 01901 if (!lfs->rcache.buffer) { 01902 return LFS_ERR_NOMEM; 01903 } 01904 } 01905 01906 // setup program cache 01907 lfs->pcache.block = 0xffffffff; 01908 if (lfs->cfg->prog_buffer) { 01909 lfs->pcache.buffer = lfs->cfg->prog_buffer; 01910 } else { 01911 lfs->pcache.buffer = malloc(lfs->cfg->prog_size); 01912 if (!lfs->pcache.buffer) { 01913 return LFS_ERR_NOMEM; 01914 } 01915 } 01916 01917 // setup lookahead, round down to nearest 32-bits 01918 assert(lfs->cfg->lookahead % 32 == 0); 01919 assert(lfs->cfg->lookahead > 0); 01920 if (lfs->cfg->lookahead_buffer) { 01921 lfs->free.buffer = lfs->cfg->lookahead_buffer; 01922 } else { 01923 lfs->free.buffer = malloc(lfs->cfg->lookahead/8); 01924 if (!lfs->free.buffer) { 01925 return LFS_ERR_NOMEM; 01926 } 01927 } 01928 01929 // check that the block size is large enough to fit ctz pointers 01930 assert(4*lfs_npw2(0xffffffff / (lfs->cfg->block_size-2*4)) 01931 <= lfs->cfg->block_size); 01932 01933 // setup default state 01934 lfs->root[0] = 0xffffffff; 01935 lfs->root[1] = 0xffffffff; 01936 lfs->files = NULL; 01937 lfs->dirs = NULL; 01938 lfs->deorphaned = false; 01939 01940 return 0; 01941 } 01942 01943 static int lfs_deinit(lfs_t *lfs) { 01944 // free allocated memory 01945 if (!lfs->cfg->read_buffer) { 01946 free(lfs->rcache.buffer); 01947 } 01948 01949 if (!lfs->cfg->prog_buffer) { 01950 free(lfs->pcache.buffer); 01951 } 01952 01953 if (!lfs->cfg->lookahead_buffer) { 01954 free(lfs->free.buffer); 01955 } 01956 01957 return 0; 01958 } 01959 01960 int lfs_format(lfs_t *lfs, const struct lfs_config *cfg) { 01961 int err = lfs_init(lfs, cfg); 01962 if (err) { 01963 return err; 01964 } 01965 01966 // create free lookahead 01967 memset(lfs->free.buffer, 0, lfs->cfg->lookahead/8); 01968 lfs->free.begin = 0; 01969 lfs->free.off = 0; 01970 lfs->free.end = lfs->free.begin + lfs->free.off + lfs->cfg->block_count; 01971 01972 // create superblock dir 01973 lfs_alloc_ack(lfs); 01974 lfs_dir_t superdir; 01975 err = lfs_dir_alloc(lfs, &superdir); 01976 if (err) { 01977 return err; 01978 } 01979 01980 // write root directory 01981 lfs_dir_t root; 01982 err = lfs_dir_alloc(lfs, &root); 01983 if (err) { 01984 return err; 01985 } 01986 01987 err = lfs_dir_commit(lfs, &root, NULL, 0); 01988 if (err) { 01989 return err; 01990 } 01991 01992 lfs->root[0] = root.pair[0]; 01993 lfs->root[1] = root.pair[1]; 01994 01995 // write superblocks 01996 lfs_superblock_t superblock = { 01997 .off = sizeof(superdir.d), 01998 .d.type = LFS_TYPE_SUPERBLOCK, 01999 .d.elen = sizeof(superblock.d) - sizeof(superblock.d.magic) - 4, 02000 .d.nlen = sizeof(superblock.d.magic), 02001 .d.version = 0x00010001, 02002 .d.magic = {"littlefs"}, 02003 .d.block_size = lfs->cfg->block_size, 02004 .d.block_count = lfs->cfg->block_count, 02005 .d.root = {lfs->root[0], lfs->root[1]}, 02006 }; 02007 superdir.d.tail[0] = root.pair[0]; 02008 superdir.d.tail[1] = root.pair[1]; 02009 superdir.d.size = sizeof(superdir.d) + sizeof(superblock.d) + 4; 02010 02011 // write both pairs to be safe 02012 bool valid = false; 02013 for (int i = 0; i < 2; i++) { 02014 int err = lfs_dir_commit(lfs, &superdir, (struct lfs_region[]){ 02015 {sizeof(superdir.d), sizeof(superblock.d), 02016 &superblock.d, sizeof(superblock.d)} 02017 }, 1); 02018 if (err && err != LFS_ERR_CORRUPT) { 02019 return err; 02020 } 02021 02022 valid = valid || !err; 02023 } 02024 02025 if (!valid) { 02026 return LFS_ERR_CORRUPT; 02027 } 02028 02029 // sanity check that fetch works 02030 err = lfs_dir_fetch(lfs, &superdir, (const lfs_block_t[2]){0, 1}); 02031 if (err) { 02032 return err; 02033 } 02034 02035 lfs_alloc_ack(lfs); 02036 return lfs_deinit(lfs); 02037 } 02038 02039 int lfs_mount(lfs_t *lfs, const struct lfs_config *cfg) { 02040 int err = lfs_init(lfs, cfg); 02041 if (err) { 02042 return err; 02043 } 02044 02045 // setup free lookahead, rewind so first allocation triggers a scan 02046 lfs->free.begin = -lfs_min(lfs->cfg->lookahead, lfs->cfg->block_count); 02047 lfs->free.off = -lfs->free.begin; 02048 lfs->free.end = lfs->free.begin + lfs->free.off + lfs->cfg->block_count; 02049 02050 // load superblock 02051 lfs_dir_t dir; 02052 lfs_superblock_t superblock; 02053 err = lfs_dir_fetch(lfs, &dir, (const lfs_block_t[2]){0, 1}); 02054 if (err && err != LFS_ERR_CORRUPT) { 02055 return err; 02056 } 02057 02058 if (!err) { 02059 int err = lfs_bd_read(lfs, dir.pair[0], sizeof(dir.d), 02060 &superblock.d, sizeof(superblock.d)); 02061 if (err) { 02062 return err; 02063 } 02064 02065 lfs->root[0] = superblock.d.root[0]; 02066 lfs->root[1] = superblock.d.root[1]; 02067 } 02068 02069 if (err || memcmp(superblock.d.magic, "littlefs", 8) != 0) { 02070 LFS_ERROR("Invalid superblock at %ld %ld", dir.pair[0], dir.pair[1]); 02071 return LFS_ERR_CORRUPT; 02072 } 02073 02074 if (superblock.d.version > (0x00010001 | 0x0000ffff)) { 02075 LFS_ERROR("Invalid version %ld.%ld", 02076 0xffff & (superblock.d.version >> 16), 02077 0xffff & (superblock.d.version >> 0)); 02078 return LFS_ERR_INVAL; 02079 } 02080 02081 return 0; 02082 } 02083 02084 int lfs_unmount(lfs_t *lfs) { 02085 return lfs_deinit(lfs); 02086 } 02087 02088 02089 /// Littlefs specific operations /// 02090 int lfs_traverse(lfs_t *lfs, int (*cb)(void*, lfs_block_t), void *data) { 02091 if (lfs_pairisnull(lfs->root)) { 02092 return 0; 02093 } 02094 02095 // iterate over metadata pairs 02096 lfs_dir_t dir; 02097 lfs_entry_t entry; 02098 lfs_block_t cwd[2] = {0, 1}; 02099 02100 while (true) { 02101 for (int i = 0; i < 2; i++) { 02102 int err = cb(data, cwd[i]); 02103 if (err) { 02104 return err; 02105 } 02106 } 02107 02108 int err = lfs_dir_fetch(lfs, &dir, cwd); 02109 if (err) { 02110 return err; 02111 } 02112 02113 // iterate over contents 02114 while (dir.off + sizeof(entry.d) <= (0x7fffffff & dir.d.size)-4) { 02115 int err = lfs_bd_read(lfs, dir.pair[0], dir.off, 02116 &entry.d, sizeof(entry.d)); 02117 if (err) { 02118 return err; 02119 } 02120 02121 dir.off += lfs_entry_size(&entry); 02122 if ((0x70 & entry.d.type) == (0x70 & LFS_TYPE_REG)) { 02123 int err = lfs_ctz_traverse(lfs, &lfs->rcache, NULL, 02124 entry.d.u.file.head, entry.d.u.file.size, cb, data); 02125 if (err) { 02126 return err; 02127 } 02128 } 02129 } 02130 02131 cwd[0] = dir.d.tail[0]; 02132 cwd[1] = dir.d.tail[1]; 02133 02134 if (lfs_pairisnull(cwd)) { 02135 break; 02136 } 02137 } 02138 02139 // iterate over any open files 02140 for (lfs_file_t *f = lfs->files; f; f = f->next) { 02141 if (f->flags & LFS_F_DIRTY) { 02142 int err = lfs_ctz_traverse(lfs, &lfs->rcache, &f->cache, 02143 f->head, f->size, cb, data); 02144 if (err) { 02145 return err; 02146 } 02147 } 02148 02149 if (f->flags & LFS_F_WRITING) { 02150 int err = lfs_ctz_traverse(lfs, &lfs->rcache, &f->cache, 02151 f->block, f->pos, cb, data); 02152 if (err) { 02153 return err; 02154 } 02155 } 02156 } 02157 02158 return 0; 02159 } 02160 02161 static int lfs_pred(lfs_t *lfs, const lfs_block_t dir[2], lfs_dir_t *pdir) { 02162 if (lfs_pairisnull(lfs->root)) { 02163 return 0; 02164 } 02165 02166 // iterate over all directory directory entries 02167 int err = lfs_dir_fetch(lfs, pdir, (const lfs_block_t[2]){0, 1}); 02168 if (err) { 02169 return err; 02170 } 02171 02172 while (!lfs_pairisnull(pdir->d.tail)) { 02173 if (lfs_paircmp(pdir->d.tail, dir) == 0) { 02174 return true; 02175 } 02176 02177 int err = lfs_dir_fetch(lfs, pdir, pdir->d.tail); 02178 if (err) { 02179 return err; 02180 } 02181 } 02182 02183 return false; 02184 } 02185 02186 static int lfs_parent(lfs_t *lfs, const lfs_block_t dir[2], 02187 lfs_dir_t *parent, lfs_entry_t *entry) { 02188 if (lfs_pairisnull(lfs->root)) { 02189 return 0; 02190 } 02191 02192 parent->d.tail[0] = 0; 02193 parent->d.tail[1] = 1; 02194 02195 // iterate over all directory directory entries 02196 while (!lfs_pairisnull(parent->d.tail)) { 02197 int err = lfs_dir_fetch(lfs, parent, parent->d.tail); 02198 if (err) { 02199 return err; 02200 } 02201 02202 while (true) { 02203 int err = lfs_dir_next(lfs, parent, entry); 02204 if (err && err != LFS_ERR_NOENT) { 02205 return err; 02206 } 02207 02208 if (err == LFS_ERR_NOENT) { 02209 break; 02210 } 02211 02212 if (((0x70 & entry->d.type) == (0x70 & LFS_TYPE_DIR)) && 02213 lfs_paircmp(entry->d.u.dir, dir) == 0) { 02214 return true; 02215 } 02216 } 02217 } 02218 02219 return false; 02220 } 02221 02222 static int lfs_moved(lfs_t *lfs, const void *e) { 02223 if (lfs_pairisnull(lfs->root)) { 02224 return 0; 02225 } 02226 02227 // skip superblock 02228 lfs_dir_t cwd; 02229 int err = lfs_dir_fetch(lfs, &cwd, (const lfs_block_t[2]){0, 1}); 02230 if (err) { 02231 return err; 02232 } 02233 02234 // iterate over all directory directory entries 02235 lfs_entry_t entry; 02236 while (!lfs_pairisnull(cwd.d.tail)) { 02237 int err = lfs_dir_fetch(lfs, &cwd, cwd.d.tail); 02238 if (err) { 02239 return err; 02240 } 02241 02242 while (true) { 02243 int err = lfs_dir_next(lfs, &cwd, &entry); 02244 if (err && err != LFS_ERR_NOENT) { 02245 return err; 02246 } 02247 02248 if (err == LFS_ERR_NOENT) { 02249 break; 02250 } 02251 02252 if (!(0x80 & entry.d.type) && 02253 memcmp(&entry.d.u, e, sizeof(entry.d.u)) == 0) { 02254 return true; 02255 } 02256 } 02257 } 02258 02259 return false; 02260 } 02261 02262 static int lfs_relocate(lfs_t *lfs, 02263 const lfs_block_t oldpair[2], const lfs_block_t newpair[2]) { 02264 // find parent 02265 lfs_dir_t parent; 02266 lfs_entry_t entry; 02267 int res = lfs_parent(lfs, oldpair, &parent, &entry); 02268 if (res < 0) { 02269 return res; 02270 } 02271 02272 if (res) { 02273 // update disk, this creates a desync 02274 entry.d.u.dir[0] = newpair[0]; 02275 entry.d.u.dir[1] = newpair[1]; 02276 02277 int err = lfs_dir_update(lfs, &parent, &entry, NULL); 02278 if (err) { 02279 return err; 02280 } 02281 02282 // update internal root 02283 if (lfs_paircmp(oldpair, lfs->root) == 0) { 02284 LFS_DEBUG("Relocating root %ld %ld", newpair[0], newpair[1]); 02285 lfs->root[0] = newpair[0]; 02286 lfs->root[1] = newpair[1]; 02287 } 02288 02289 // clean up bad block, which should now be a desync 02290 return lfs_deorphan(lfs); 02291 } 02292 02293 // find pred 02294 res = lfs_pred(lfs, oldpair, &parent); 02295 if (res < 0) { 02296 return res; 02297 } 02298 02299 if (res) { 02300 // just replace bad pair, no desync can occur 02301 parent.d.tail[0] = newpair[0]; 02302 parent.d.tail[1] = newpair[1]; 02303 02304 return lfs_dir_commit(lfs, &parent, NULL, 0); 02305 } 02306 02307 // couldn't find dir, must be new 02308 return 0; 02309 } 02310 02311 int lfs_deorphan(lfs_t *lfs) { 02312 lfs->deorphaned = true; 02313 02314 if (lfs_pairisnull(lfs->root)) { 02315 return 0; 02316 } 02317 02318 lfs_dir_t pdir = {.d.size = 0x80000000}; 02319 lfs_dir_t cwd = {.d.tail[0] = 0, .d.tail[1] = 1}; 02320 02321 // iterate over all directory directory entries 02322 while (!lfs_pairisnull(cwd.d.tail)) { 02323 int err = lfs_dir_fetch(lfs, &cwd, cwd.d.tail); 02324 if (err) { 02325 return err; 02326 } 02327 02328 // check head blocks for orphans 02329 if (!(0x80000000 & pdir.d.size)) { 02330 // check if we have a parent 02331 lfs_dir_t parent; 02332 lfs_entry_t entry; 02333 int res = lfs_parent(lfs, pdir.d.tail, &parent, &entry); 02334 if (res < 0) { 02335 return res; 02336 } 02337 02338 if (!res) { 02339 // we are an orphan 02340 LFS_DEBUG("Found orphan %ld %ld", 02341 pdir.d.tail[0], pdir.d.tail[1]); 02342 02343 pdir.d.tail[0] = cwd.d.tail[0]; 02344 pdir.d.tail[1] = cwd.d.tail[1]; 02345 02346 err = lfs_dir_commit(lfs, &pdir, NULL, 0); 02347 if (err) { 02348 return err; 02349 } 02350 02351 break; 02352 } 02353 02354 if (!lfs_pairsync(entry.d.u.dir, pdir.d.tail)) { 02355 // we have desynced 02356 LFS_DEBUG("Found desync %ld %ld", 02357 entry.d.u.dir[0], entry.d.u.dir[1]); 02358 02359 pdir.d.tail[0] = entry.d.u.dir[0]; 02360 pdir.d.tail[1] = entry.d.u.dir[1]; 02361 02362 err = lfs_dir_commit(lfs, &pdir, NULL, 0); 02363 if (err) { 02364 return err; 02365 } 02366 02367 break; 02368 } 02369 } 02370 02371 // check entries for moves 02372 lfs_entry_t entry; 02373 while (true) { 02374 int err = lfs_dir_next(lfs, &cwd, &entry); 02375 if (err && err != LFS_ERR_NOENT) { 02376 return err; 02377 } 02378 02379 if (err == LFS_ERR_NOENT) { 02380 break; 02381 } 02382 02383 // found moved entry 02384 if (entry.d.type & 0x80) { 02385 int moved = lfs_moved(lfs, &entry.d.u); 02386 if (moved < 0) { 02387 return moved; 02388 } 02389 02390 if (moved) { 02391 LFS_DEBUG("Found move %ld %ld", 02392 entry.d.u.dir[0], entry.d.u.dir[1]); 02393 int err = lfs_dir_remove(lfs, &cwd, &entry); 02394 if (err) { 02395 return err; 02396 } 02397 } else { 02398 LFS_DEBUG("Found partial move %ld %ld", 02399 entry.d.u.dir[0], entry.d.u.dir[1]); 02400 entry.d.type &= ~0x80; 02401 int err = lfs_dir_update(lfs, &cwd, &entry, NULL); 02402 if (err) { 02403 return err; 02404 } 02405 } 02406 } 02407 } 02408 02409 memcpy(&pdir, &cwd, sizeof(pdir)); 02410 } 02411 02412 return 0; 02413 } 02414
Generated on Tue Jul 12 2022 13:24:47 by
1.7.2