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