takashi kadono
/
Nucleo_446
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.
Embed:
(wiki syntax)
Show/hide line numbers
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 (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_zero(lfs, &file->cache); 01377 01378 // add to list of files 01379 file->next = lfs->files; 01380 lfs->files = file; 01381 01382 return 0; 01383 } 01384 01385 int lfs_file_open(lfs_t *lfs, lfs_file_t *file, 01386 const char *path, int flags) { 01387 return lfs_file_opencfg(lfs, file, path, flags, NULL); 01388 } 01389 01390 int lfs_file_close(lfs_t *lfs, lfs_file_t *file) { 01391 int err = lfs_file_sync(lfs, file); 01392 01393 // remove from list of files 01394 for (lfs_file_t **p = &lfs->files; *p; p = &(*p)->next) { 01395 if (*p == file) { 01396 *p = file->next; 01397 break; 01398 } 01399 } 01400 01401 // clean up memory 01402 if (!(file->cfg && file->cfg->buffer) && !lfs->cfg->file_buffer) { 01403 lfs_free(file->cache.buffer); 01404 } 01405 01406 return err; 01407 } 01408 01409 static int lfs_file_relocate(lfs_t *lfs, lfs_file_t *file) { 01410 relocate: 01411 LFS_DEBUG("Bad block at %" PRIu32, file->block); 01412 01413 // just relocate what exists into new block 01414 lfs_block_t nblock; 01415 int err = lfs_alloc(lfs, &nblock); 01416 if (err) { 01417 return err; 01418 } 01419 01420 err = lfs_bd_erase(lfs, nblock); 01421 if (err) { 01422 if (err == LFS_ERR_CORRUPT) { 01423 goto relocate; 01424 } 01425 return err; 01426 } 01427 01428 // either read from dirty cache or disk 01429 for (lfs_off_t i = 0; i < file->off; i++) { 01430 uint8_t data; 01431 err = lfs_cache_read(lfs, &lfs->rcache, &file->cache, 01432 file->block, i, &data, 1); 01433 if (err) { 01434 return err; 01435 } 01436 01437 err = lfs_cache_prog(lfs, &lfs->pcache, &lfs->rcache, 01438 nblock, i, &data, 1); 01439 if (err) { 01440 if (err == LFS_ERR_CORRUPT) { 01441 goto relocate; 01442 } 01443 return err; 01444 } 01445 } 01446 01447 // copy over new state of file 01448 memcpy(file->cache.buffer, lfs->pcache.buffer, lfs->cfg->prog_size); 01449 file->cache.block = lfs->pcache.block; 01450 file->cache.off = lfs->pcache.off; 01451 lfs_cache_zero(lfs, &lfs->pcache); 01452 01453 file->block = nblock; 01454 return 0; 01455 } 01456 01457 static int lfs_file_flush(lfs_t *lfs, lfs_file_t *file) { 01458 if (file->flags & LFS_F_READING) { 01459 // just drop read cache 01460 lfs_cache_drop(lfs, &file->cache); 01461 file->flags &= ~LFS_F_READING; 01462 } 01463 01464 if (file->flags & LFS_F_WRITING) { 01465 lfs_off_t pos = file->pos; 01466 01467 // copy over anything after current branch 01468 lfs_file_t orig = { 01469 .head = file->head, 01470 .size = file->size, 01471 .flags = LFS_O_RDONLY, 01472 .pos = file->pos, 01473 .cache = lfs->rcache, 01474 }; 01475 lfs_cache_drop(lfs, &lfs->rcache); 01476 01477 while (file->pos < file->size) { 01478 // copy over a byte at a time, leave it up to caching 01479 // to make this efficient 01480 uint8_t data; 01481 lfs_ssize_t res = lfs_file_read(lfs, &orig, &data, 1); 01482 if (res < 0) { 01483 return res; 01484 } 01485 01486 res = lfs_file_write(lfs, file, &data, 1); 01487 if (res < 0) { 01488 return res; 01489 } 01490 01491 // keep our reference to the rcache in sync 01492 if (lfs->rcache.block != 0xffffffff) { 01493 lfs_cache_drop(lfs, &orig.cache); 01494 lfs_cache_drop(lfs, &lfs->rcache); 01495 } 01496 } 01497 01498 // write out what we have 01499 while (true) { 01500 int err = lfs_cache_flush(lfs, &file->cache, &lfs->rcache); 01501 if (err) { 01502 if (err == LFS_ERR_CORRUPT) { 01503 goto relocate; 01504 } 01505 return err; 01506 } 01507 01508 break; 01509 relocate: 01510 err = lfs_file_relocate(lfs, file); 01511 if (err) { 01512 return err; 01513 } 01514 } 01515 01516 // actual file updates 01517 file->head = file->block; 01518 file->size = file->pos; 01519 file->flags &= ~LFS_F_WRITING; 01520 file->flags |= LFS_F_DIRTY; 01521 01522 file->pos = pos; 01523 } 01524 01525 return 0; 01526 } 01527 01528 int lfs_file_sync(lfs_t *lfs, lfs_file_t *file) { 01529 int err = lfs_file_flush(lfs, file); 01530 if (err) { 01531 return err; 01532 } 01533 01534 if ((file->flags & LFS_F_DIRTY) && 01535 !(file->flags & LFS_F_ERRED) && 01536 !lfs_pairisnull(file->pair)) { 01537 // update dir entry 01538 lfs_dir_t cwd; 01539 err = lfs_dir_fetch(lfs, &cwd, file->pair); 01540 if (err) { 01541 return err; 01542 } 01543 01544 lfs_entry_t entry = {.off = file->poff}; 01545 err = lfs_bd_read(lfs, cwd.pair[0], entry.off, 01546 &entry.d, sizeof(entry.d)); 01547 lfs_entry_fromle32(&entry.d); 01548 if (err) { 01549 return err; 01550 } 01551 01552 LFS_ASSERT(entry.d.type == LFS_TYPE_REG); 01553 entry.d.u.file.head = file->head; 01554 entry.d.u.file.size = file->size; 01555 01556 err = lfs_dir_update(lfs, &cwd, &entry, NULL); 01557 if (err) { 01558 return err; 01559 } 01560 01561 file->flags &= ~LFS_F_DIRTY; 01562 } 01563 01564 return 0; 01565 } 01566 01567 lfs_ssize_t lfs_file_read(lfs_t *lfs, lfs_file_t *file, 01568 void *buffer, lfs_size_t size) { 01569 uint8_t *data = buffer; 01570 lfs_size_t nsize = size; 01571 01572 if ((file->flags & 3) == LFS_O_WRONLY) { 01573 return LFS_ERR_BADF; 01574 } 01575 01576 if (file->flags & LFS_F_WRITING) { 01577 // flush out any writes 01578 int err = lfs_file_flush(lfs, file); 01579 if (err) { 01580 return err; 01581 } 01582 } 01583 01584 if (file->pos >= file->size) { 01585 // eof if past end 01586 return 0; 01587 } 01588 01589 size = lfs_min(size, file->size - file->pos); 01590 nsize = size; 01591 01592 while (nsize > 0) { 01593 // check if we need a new block 01594 if (!(file->flags & LFS_F_READING) || 01595 file->off == lfs->cfg->block_size) { 01596 int err = lfs_ctz_find(lfs, &file->cache, NULL, 01597 file->head, file->size, 01598 file->pos, &file->block, &file->off); 01599 if (err) { 01600 return err; 01601 } 01602 01603 file->flags |= LFS_F_READING; 01604 } 01605 01606 // read as much as we can in current block 01607 lfs_size_t diff = lfs_min(nsize, lfs->cfg->block_size - file->off); 01608 int err = lfs_cache_read(lfs, &file->cache, NULL, 01609 file->block, file->off, data, diff); 01610 if (err) { 01611 return err; 01612 } 01613 01614 file->pos += diff; 01615 file->off += diff; 01616 data += diff; 01617 nsize -= diff; 01618 } 01619 01620 return size; 01621 } 01622 01623 lfs_ssize_t lfs_file_write(lfs_t *lfs, lfs_file_t *file, 01624 const void *buffer, lfs_size_t size) { 01625 const uint8_t *data = buffer; 01626 lfs_size_t nsize = size; 01627 01628 if ((file->flags & 3) == LFS_O_RDONLY) { 01629 return LFS_ERR_BADF; 01630 } 01631 01632 if (file->flags & LFS_F_READING) { 01633 // drop any reads 01634 int err = lfs_file_flush(lfs, file); 01635 if (err) { 01636 return err; 01637 } 01638 } 01639 01640 if ((file->flags & LFS_O_APPEND) && file->pos < file->size) { 01641 file->pos = file->size; 01642 } 01643 01644 if (!(file->flags & LFS_F_WRITING) && file->pos > file->size) { 01645 // fill with zeros 01646 lfs_off_t pos = file->pos; 01647 file->pos = file->size; 01648 01649 while (file->pos < pos) { 01650 lfs_ssize_t res = lfs_file_write(lfs, file, &(uint8_t){0}, 1); 01651 if (res < 0) { 01652 return res; 01653 } 01654 } 01655 } 01656 01657 while (nsize > 0) { 01658 // check if we need a new block 01659 if (!(file->flags & LFS_F_WRITING) || 01660 file->off == lfs->cfg->block_size) { 01661 if (!(file->flags & LFS_F_WRITING) && file->pos > 0) { 01662 // find out which block we're extending from 01663 int err = lfs_ctz_find(lfs, &file->cache, NULL, 01664 file->head, file->size, 01665 file->pos-1, &file->block, &file->off); 01666 if (err) { 01667 file->flags |= LFS_F_ERRED; 01668 return err; 01669 } 01670 01671 // mark cache as dirty since we may have read data into it 01672 lfs_cache_zero(lfs, &file->cache); 01673 } 01674 01675 // extend file with new blocks 01676 lfs_alloc_ack(lfs); 01677 int err = lfs_ctz_extend(lfs, &lfs->rcache, &file->cache, 01678 file->block, file->pos, 01679 &file->block, &file->off); 01680 if (err) { 01681 file->flags |= LFS_F_ERRED; 01682 return err; 01683 } 01684 01685 file->flags |= LFS_F_WRITING; 01686 } 01687 01688 // program as much as we can in current block 01689 lfs_size_t diff = lfs_min(nsize, lfs->cfg->block_size - file->off); 01690 while (true) { 01691 int err = lfs_cache_prog(lfs, &file->cache, &lfs->rcache, 01692 file->block, file->off, data, diff); 01693 if (err) { 01694 if (err == LFS_ERR_CORRUPT) { 01695 goto relocate; 01696 } 01697 file->flags |= LFS_F_ERRED; 01698 return err; 01699 } 01700 01701 break; 01702 relocate: 01703 err = lfs_file_relocate(lfs, file); 01704 if (err) { 01705 file->flags |= LFS_F_ERRED; 01706 return err; 01707 } 01708 } 01709 01710 file->pos += diff; 01711 file->off += diff; 01712 data += diff; 01713 nsize -= diff; 01714 01715 lfs_alloc_ack(lfs); 01716 } 01717 01718 file->flags &= ~LFS_F_ERRED; 01719 return size; 01720 } 01721 01722 lfs_soff_t lfs_file_seek(lfs_t *lfs, lfs_file_t *file, 01723 lfs_soff_t off, int whence) { 01724 // write out everything beforehand, may be noop if rdonly 01725 int err = lfs_file_flush(lfs, file); 01726 if (err) { 01727 return err; 01728 } 01729 01730 // update pos 01731 if (whence == LFS_SEEK_SET) { 01732 file->pos = off; 01733 } else if (whence == LFS_SEEK_CUR) { 01734 if (off < 0 && (lfs_off_t)-off > file->pos) { 01735 return LFS_ERR_INVAL; 01736 } 01737 01738 file->pos = file->pos + off; 01739 } else if (whence == LFS_SEEK_END) { 01740 if (off < 0 && (lfs_off_t)-off > file->size) { 01741 return LFS_ERR_INVAL; 01742 } 01743 01744 file->pos = file->size + off; 01745 } 01746 01747 return file->pos; 01748 } 01749 01750 int lfs_file_truncate(lfs_t *lfs, lfs_file_t *file, lfs_off_t size) { 01751 if ((file->flags & 3) == LFS_O_RDONLY) { 01752 return LFS_ERR_BADF; 01753 } 01754 01755 lfs_off_t oldsize = lfs_file_size(lfs, file); 01756 if (size < oldsize) { 01757 // need to flush since directly changing metadata 01758 int err = lfs_file_flush(lfs, file); 01759 if (err) { 01760 return err; 01761 } 01762 01763 // lookup new head in ctz skip list 01764 err = lfs_ctz_find(lfs, &file->cache, NULL, 01765 file->head, file->size, 01766 size, &file->head, &(lfs_off_t){0}); 01767 if (err) { 01768 return err; 01769 } 01770 01771 file->size = size; 01772 file->flags |= LFS_F_DIRTY; 01773 } else if (size > oldsize) { 01774 lfs_off_t pos = file->pos; 01775 01776 // flush+seek if not already at end 01777 if (file->pos != oldsize) { 01778 int err = lfs_file_seek(lfs, file, 0, LFS_SEEK_END); 01779 if (err < 0) { 01780 return err; 01781 } 01782 } 01783 01784 // fill with zeros 01785 while (file->pos < size) { 01786 lfs_ssize_t res = lfs_file_write(lfs, file, &(uint8_t){0}, 1); 01787 if (res < 0) { 01788 return res; 01789 } 01790 } 01791 01792 // restore pos 01793 int err = lfs_file_seek(lfs, file, pos, LFS_SEEK_SET); 01794 if (err < 0) { 01795 return err; 01796 } 01797 } 01798 01799 return 0; 01800 } 01801 01802 lfs_soff_t lfs_file_tell(lfs_t *lfs, lfs_file_t *file) { 01803 (void)lfs; 01804 return file->pos; 01805 } 01806 01807 int lfs_file_rewind(lfs_t *lfs, lfs_file_t *file) { 01808 lfs_soff_t res = lfs_file_seek(lfs, file, 0, LFS_SEEK_SET); 01809 if (res < 0) { 01810 return res; 01811 } 01812 01813 return 0; 01814 } 01815 01816 lfs_soff_t lfs_file_size(lfs_t *lfs, lfs_file_t *file) { 01817 (void)lfs; 01818 if (file->flags & LFS_F_WRITING) { 01819 return lfs_max(file->pos, file->size); 01820 } else { 01821 return file->size; 01822 } 01823 } 01824 01825 01826 /// General fs operations /// 01827 int lfs_stat(lfs_t *lfs, const char *path, struct lfs_info *info) { 01828 lfs_dir_t cwd; 01829 lfs_entry_t entry; 01830 int err = lfs_dir_find(lfs, &cwd, &entry, &path); 01831 if (err) { 01832 return err; 01833 } 01834 01835 memset(info, 0, sizeof(*info)); 01836 info->type = entry.d.type; 01837 if (info->type == LFS_TYPE_REG) { 01838 info->size = entry.d.u.file.size; 01839 } 01840 01841 if (lfs_paircmp(entry.d.u.dir, lfs->root) == 0) { 01842 strcpy(info->name, "/"); 01843 } else { 01844 err = lfs_bd_read(lfs, cwd.pair[0], 01845 entry.off + 4+entry.d.elen+entry.d.alen, 01846 info->name, entry.d.nlen); 01847 if (err) { 01848 return err; 01849 } 01850 } 01851 01852 return 0; 01853 } 01854 01855 int lfs_remove(lfs_t *lfs, const char *path) { 01856 // deorphan if we haven't yet, needed at most once after poweron 01857 if (!lfs->deorphaned) { 01858 int err = lfs_deorphan(lfs); 01859 if (err) { 01860 return err; 01861 } 01862 } 01863 01864 lfs_dir_t cwd; 01865 lfs_entry_t entry; 01866 int err = lfs_dir_find(lfs, &cwd, &entry, &path); 01867 if (err) { 01868 return err; 01869 } 01870 01871 lfs_dir_t dir; 01872 if (entry.d.type == LFS_TYPE_DIR) { 01873 // must be empty before removal, checking size 01874 // without masking top bit checks for any case where 01875 // dir is not empty 01876 err = lfs_dir_fetch(lfs, &dir, entry.d.u.dir); 01877 if (err) { 01878 return err; 01879 } else if (dir.d.size != sizeof(dir.d)+4) { 01880 return LFS_ERR_NOTEMPTY; 01881 } 01882 } 01883 01884 // remove the entry 01885 err = lfs_dir_remove(lfs, &cwd, &entry); 01886 if (err) { 01887 return err; 01888 } 01889 01890 // if we were a directory, find pred, replace tail 01891 if (entry.d.type == LFS_TYPE_DIR) { 01892 int res = lfs_pred(lfs, dir.pair, &cwd); 01893 if (res < 0) { 01894 return res; 01895 } 01896 01897 LFS_ASSERT(res); // must have pred 01898 cwd.d.tail[0] = dir.d.tail[0]; 01899 cwd.d.tail[1] = dir.d.tail[1]; 01900 01901 err = lfs_dir_commit(lfs, &cwd, NULL, 0); 01902 if (err) { 01903 return err; 01904 } 01905 } 01906 01907 return 0; 01908 } 01909 01910 int lfs_rename(lfs_t *lfs, const char *oldpath, const char *newpath) { 01911 // deorphan if we haven't yet, needed at most once after poweron 01912 if (!lfs->deorphaned) { 01913 int err = lfs_deorphan(lfs); 01914 if (err) { 01915 return err; 01916 } 01917 } 01918 01919 // find old entry 01920 lfs_dir_t oldcwd; 01921 lfs_entry_t oldentry; 01922 int err = lfs_dir_find(lfs, &oldcwd, &oldentry, &oldpath); 01923 if (err) { 01924 return err; 01925 } 01926 01927 // allocate new entry 01928 lfs_dir_t newcwd; 01929 lfs_entry_t preventry; 01930 err = lfs_dir_find(lfs, &newcwd, &preventry, &newpath); 01931 if (err && (err != LFS_ERR_NOENT || strchr(newpath, '/') != NULL)) { 01932 return err; 01933 } 01934 01935 bool prevexists = (err != LFS_ERR_NOENT); 01936 bool samepair = (lfs_paircmp(oldcwd.pair, newcwd.pair) == 0); 01937 01938 // must have same type 01939 if (prevexists && preventry.d.type != oldentry.d.type) { 01940 return LFS_ERR_ISDIR; 01941 } 01942 01943 lfs_dir_t dir; 01944 if (prevexists && preventry.d.type == LFS_TYPE_DIR) { 01945 // must be empty before removal, checking size 01946 // without masking top bit checks for any case where 01947 // dir is not empty 01948 err = lfs_dir_fetch(lfs, &dir, preventry.d.u.dir); 01949 if (err) { 01950 return err; 01951 } else if (dir.d.size != sizeof(dir.d)+4) { 01952 return LFS_ERR_NOTEMPTY; 01953 } 01954 } 01955 01956 // mark as moving 01957 oldentry.d.type |= 0x80; 01958 err = lfs_dir_update(lfs, &oldcwd, &oldentry, NULL); 01959 if (err) { 01960 return err; 01961 } 01962 01963 // update pair if newcwd == oldcwd 01964 if (samepair) { 01965 newcwd = oldcwd; 01966 } 01967 01968 // move to new location 01969 lfs_entry_t newentry = preventry; 01970 newentry.d = oldentry.d; 01971 newentry.d.type &= ~0x80; 01972 newentry.d.nlen = strlen(newpath); 01973 01974 if (prevexists) { 01975 err = lfs_dir_update(lfs, &newcwd, &newentry, newpath); 01976 if (err) { 01977 return err; 01978 } 01979 } else { 01980 err = lfs_dir_append(lfs, &newcwd, &newentry, newpath); 01981 if (err) { 01982 return err; 01983 } 01984 } 01985 01986 // update pair if newcwd == oldcwd 01987 if (samepair) { 01988 oldcwd = newcwd; 01989 } 01990 01991 // remove old entry 01992 err = lfs_dir_remove(lfs, &oldcwd, &oldentry); 01993 if (err) { 01994 return err; 01995 } 01996 01997 // if we were a directory, find pred, replace tail 01998 if (prevexists && preventry.d.type == LFS_TYPE_DIR) { 01999 int res = lfs_pred(lfs, dir.pair, &newcwd); 02000 if (res < 0) { 02001 return res; 02002 } 02003 02004 LFS_ASSERT(res); // must have pred 02005 newcwd.d.tail[0] = dir.d.tail[0]; 02006 newcwd.d.tail[1] = dir.d.tail[1]; 02007 02008 err = lfs_dir_commit(lfs, &newcwd, NULL, 0); 02009 if (err) { 02010 return err; 02011 } 02012 } 02013 02014 return 0; 02015 } 02016 02017 02018 /// Filesystem operations /// 02019 static void lfs_deinit(lfs_t *lfs) { 02020 // free allocated memory 02021 if (!lfs->cfg->read_buffer) { 02022 lfs_free(lfs->rcache.buffer); 02023 } 02024 02025 if (!lfs->cfg->prog_buffer) { 02026 lfs_free(lfs->pcache.buffer); 02027 } 02028 02029 if (!lfs->cfg->lookahead_buffer) { 02030 lfs_free(lfs->free.buffer); 02031 } 02032 } 02033 02034 static int lfs_init(lfs_t *lfs, const struct lfs_config *cfg) { 02035 lfs->cfg = cfg; 02036 02037 // setup read cache 02038 if (lfs->cfg->read_buffer) { 02039 lfs->rcache.buffer = lfs->cfg->read_buffer; 02040 } else { 02041 lfs->rcache.buffer = lfs_malloc(lfs->cfg->read_size); 02042 if (!lfs->rcache.buffer) { 02043 goto cleanup; 02044 } 02045 } 02046 02047 // setup program cache 02048 if (lfs->cfg->prog_buffer) { 02049 lfs->pcache.buffer = lfs->cfg->prog_buffer; 02050 } else { 02051 lfs->pcache.buffer = lfs_malloc(lfs->cfg->prog_size); 02052 if (!lfs->pcache.buffer) { 02053 goto cleanup; 02054 } 02055 } 02056 02057 // zero to avoid information leaks 02058 lfs_cache_zero(lfs, &lfs->rcache); 02059 lfs_cache_zero(lfs, &lfs->pcache); 02060 02061 // setup lookahead, round down to nearest 32-bits 02062 LFS_ASSERT(lfs->cfg->lookahead % 32 == 0); 02063 LFS_ASSERT(lfs->cfg->lookahead > 0); 02064 if (lfs->cfg->lookahead_buffer) { 02065 lfs->free.buffer = lfs->cfg->lookahead_buffer; 02066 } else { 02067 lfs->free.buffer = lfs_malloc(lfs->cfg->lookahead/8); 02068 if (!lfs->free.buffer) { 02069 goto cleanup; 02070 } 02071 } 02072 02073 // check that program and read sizes are multiples of the block size 02074 LFS_ASSERT(lfs->cfg->prog_size % lfs->cfg->read_size == 0); 02075 LFS_ASSERT(lfs->cfg->block_size % lfs->cfg->prog_size == 0); 02076 02077 // check that the block size is large enough to fit ctz pointers 02078 LFS_ASSERT(4*lfs_npw2(0xffffffff / (lfs->cfg->block_size-2*4)) 02079 <= lfs->cfg->block_size); 02080 02081 // setup default state 02082 lfs->root[0] = 0xffffffff; 02083 lfs->root[1] = 0xffffffff; 02084 lfs->files = NULL; 02085 lfs->dirs = NULL; 02086 lfs->deorphaned = false; 02087 02088 return 0; 02089 02090 cleanup: 02091 lfs_deinit(lfs); 02092 return LFS_ERR_NOMEM; 02093 } 02094 02095 int lfs_format(lfs_t *lfs, const struct lfs_config *cfg) { 02096 int err = lfs_init(lfs, cfg); 02097 if (err) { 02098 return err; 02099 } 02100 02101 // create free lookahead 02102 memset(lfs->free.buffer, 0, lfs->cfg->lookahead/8); 02103 lfs->free.off = 0; 02104 lfs->free.size = lfs_min(lfs->cfg->lookahead, lfs->cfg->block_count); 02105 lfs->free.i = 0; 02106 lfs_alloc_ack(lfs); 02107 02108 // create superblock dir 02109 lfs_dir_t superdir; 02110 err = lfs_dir_alloc(lfs, &superdir); 02111 if (err) { 02112 goto cleanup; 02113 } 02114 02115 // write root directory 02116 lfs_dir_t root; 02117 err = lfs_dir_alloc(lfs, &root); 02118 if (err) { 02119 goto cleanup; 02120 } 02121 02122 err = lfs_dir_commit(lfs, &root, NULL, 0); 02123 if (err) { 02124 goto cleanup; 02125 } 02126 02127 lfs->root[0] = root.pair[0]; 02128 lfs->root[1] = root.pair[1]; 02129 02130 // write superblocks 02131 lfs_superblock_t superblock = { 02132 .off = sizeof(superdir.d), 02133 .d.type = LFS_TYPE_SUPERBLOCK, 02134 .d.elen = sizeof(superblock.d) - sizeof(superblock.d.magic) - 4, 02135 .d.nlen = sizeof(superblock.d.magic), 02136 .d.version = LFS_DISK_VERSION, 02137 .d.magic = {"littlefs"}, 02138 .d.block_size = lfs->cfg->block_size, 02139 .d.block_count = lfs->cfg->block_count, 02140 .d.root = {lfs->root[0], lfs->root[1]}, 02141 }; 02142 superdir.d.tail[0] = root.pair[0]; 02143 superdir.d.tail[1] = root.pair[1]; 02144 superdir.d.size = sizeof(superdir.d) + sizeof(superblock.d) + 4; 02145 02146 // write both pairs to be safe 02147 lfs_superblock_tole32(&superblock.d); 02148 bool valid = false; 02149 for (int i = 0; i < 2; i++) { 02150 err = lfs_dir_commit(lfs, &superdir, (struct lfs_region[]){ 02151 {sizeof(superdir.d), sizeof(superblock.d), 02152 &superblock.d, sizeof(superblock.d)} 02153 }, 1); 02154 if (err && err != LFS_ERR_CORRUPT) { 02155 goto cleanup; 02156 } 02157 02158 valid = valid || !err; 02159 } 02160 02161 if (!valid) { 02162 err = LFS_ERR_CORRUPT; 02163 goto cleanup; 02164 } 02165 02166 // sanity check that fetch works 02167 err = lfs_dir_fetch(lfs, &superdir, (const lfs_block_t[2]){0, 1}); 02168 if (err) { 02169 goto cleanup; 02170 } 02171 02172 lfs_alloc_ack(lfs); 02173 02174 cleanup: 02175 lfs_deinit(lfs); 02176 return err; 02177 } 02178 02179 int lfs_mount(lfs_t *lfs, const struct lfs_config *cfg) { 02180 int err = lfs_init(lfs, cfg); 02181 if (err) { 02182 return err; 02183 } 02184 02185 // setup free lookahead 02186 lfs->free.off = 0; 02187 lfs->free.size = 0; 02188 lfs->free.i = 0; 02189 lfs_alloc_ack(lfs); 02190 02191 // load superblock 02192 lfs_dir_t dir; 02193 lfs_superblock_t superblock; 02194 err = lfs_dir_fetch(lfs, &dir, (const lfs_block_t[2]){0, 1}); 02195 if (err && err != LFS_ERR_CORRUPT) { 02196 goto cleanup; 02197 } 02198 02199 if (!err) { 02200 err = lfs_bd_read(lfs, dir.pair[0], sizeof(dir.d), 02201 &superblock.d, sizeof(superblock.d)); 02202 lfs_superblock_fromle32(&superblock.d); 02203 if (err) { 02204 goto cleanup; 02205 } 02206 02207 lfs->root[0] = superblock.d.root[0]; 02208 lfs->root[1] = superblock.d.root[1]; 02209 } 02210 02211 if (err || memcmp(superblock.d.magic, "littlefs", 8) != 0) { 02212 LFS_ERROR("Invalid superblock at %d %d", 0, 1); 02213 err = LFS_ERR_CORRUPT; 02214 goto cleanup; 02215 } 02216 02217 uint16_t major_version = (0xffff & (superblock.d.version >> 16)); 02218 uint16_t minor_version = (0xffff & (superblock.d.version >> 0)); 02219 if ((major_version != LFS_DISK_VERSION_MAJOR || 02220 minor_version > LFS_DISK_VERSION_MINOR)) { 02221 LFS_ERROR("Invalid version %d.%d", major_version, minor_version); 02222 err = LFS_ERR_INVAL; 02223 goto cleanup; 02224 } 02225 02226 return 0; 02227 02228 cleanup: 02229 02230 lfs_deinit(lfs); 02231 return err; 02232 } 02233 02234 int lfs_unmount(lfs_t *lfs) { 02235 lfs_deinit(lfs); 02236 return 0; 02237 } 02238 02239 02240 /// Littlefs specific operations /// 02241 int lfs_traverse(lfs_t *lfs, int (*cb)(void*, lfs_block_t), void *data) { 02242 if (lfs_pairisnull(lfs->root)) { 02243 return 0; 02244 } 02245 02246 // iterate over metadata pairs 02247 lfs_dir_t dir; 02248 lfs_entry_t entry; 02249 lfs_block_t cwd[2] = {0, 1}; 02250 02251 while (true) { 02252 for (int i = 0; i < 2; i++) { 02253 int err = cb(data, cwd[i]); 02254 if (err) { 02255 return err; 02256 } 02257 } 02258 02259 int err = lfs_dir_fetch(lfs, &dir, cwd); 02260 if (err) { 02261 return err; 02262 } 02263 02264 // iterate over contents 02265 while (dir.off + sizeof(entry.d) <= (0x7fffffff & dir.d.size)-4) { 02266 err = lfs_bd_read(lfs, dir.pair[0], dir.off, 02267 &entry.d, sizeof(entry.d)); 02268 lfs_entry_fromle32(&entry.d); 02269 if (err) { 02270 return err; 02271 } 02272 02273 dir.off += lfs_entry_size(&entry); 02274 if ((0x70 & entry.d.type) == (0x70 & LFS_TYPE_REG)) { 02275 err = lfs_ctz_traverse(lfs, &lfs->rcache, NULL, 02276 entry.d.u.file.head, entry.d.u.file.size, cb, data); 02277 if (err) { 02278 return err; 02279 } 02280 } 02281 } 02282 02283 cwd[0] = dir.d.tail[0]; 02284 cwd[1] = dir.d.tail[1]; 02285 02286 if (lfs_pairisnull(cwd)) { 02287 break; 02288 } 02289 } 02290 02291 // iterate over any open files 02292 for (lfs_file_t *f = lfs->files; f; f = f->next) { 02293 if (f->flags & LFS_F_DIRTY) { 02294 int err = lfs_ctz_traverse(lfs, &lfs->rcache, &f->cache, 02295 f->head, f->size, cb, data); 02296 if (err) { 02297 return err; 02298 } 02299 } 02300 02301 if (f->flags & LFS_F_WRITING) { 02302 int err = lfs_ctz_traverse(lfs, &lfs->rcache, &f->cache, 02303 f->block, f->pos, cb, data); 02304 if (err) { 02305 return err; 02306 } 02307 } 02308 } 02309 02310 return 0; 02311 } 02312 02313 static int lfs_pred(lfs_t *lfs, const lfs_block_t dir[2], lfs_dir_t *pdir) { 02314 if (lfs_pairisnull(lfs->root)) { 02315 return 0; 02316 } 02317 02318 // iterate over all directory directory entries 02319 int err = lfs_dir_fetch(lfs, pdir, (const lfs_block_t[2]){0, 1}); 02320 if (err) { 02321 return err; 02322 } 02323 02324 while (!lfs_pairisnull(pdir->d.tail)) { 02325 if (lfs_paircmp(pdir->d.tail, dir) == 0) { 02326 return true; 02327 } 02328 02329 err = lfs_dir_fetch(lfs, pdir, pdir->d.tail); 02330 if (err) { 02331 return err; 02332 } 02333 } 02334 02335 return false; 02336 } 02337 02338 static int lfs_parent(lfs_t *lfs, const lfs_block_t dir[2], 02339 lfs_dir_t *parent, lfs_entry_t *entry) { 02340 if (lfs_pairisnull(lfs->root)) { 02341 return 0; 02342 } 02343 02344 parent->d.tail[0] = 0; 02345 parent->d.tail[1] = 1; 02346 02347 // iterate over all directory directory entries 02348 while (!lfs_pairisnull(parent->d.tail)) { 02349 int err = lfs_dir_fetch(lfs, parent, parent->d.tail); 02350 if (err) { 02351 return err; 02352 } 02353 02354 while (true) { 02355 err = lfs_dir_next(lfs, parent, entry); 02356 if (err && err != LFS_ERR_NOENT) { 02357 return err; 02358 } 02359 02360 if (err == LFS_ERR_NOENT) { 02361 break; 02362 } 02363 02364 if (((0x70 & entry->d.type) == (0x70 & LFS_TYPE_DIR)) && 02365 lfs_paircmp(entry->d.u.dir, dir) == 0) { 02366 return true; 02367 } 02368 } 02369 } 02370 02371 return false; 02372 } 02373 02374 static int lfs_moved(lfs_t *lfs, const void *e) { 02375 if (lfs_pairisnull(lfs->root)) { 02376 return 0; 02377 } 02378 02379 // skip superblock 02380 lfs_dir_t cwd; 02381 int err = lfs_dir_fetch(lfs, &cwd, (const lfs_block_t[2]){0, 1}); 02382 if (err) { 02383 return err; 02384 } 02385 02386 // iterate over all directory directory entries 02387 lfs_entry_t entry; 02388 while (!lfs_pairisnull(cwd.d.tail)) { 02389 err = lfs_dir_fetch(lfs, &cwd, cwd.d.tail); 02390 if (err) { 02391 return err; 02392 } 02393 02394 while (true) { 02395 err = lfs_dir_next(lfs, &cwd, &entry); 02396 if (err && err != LFS_ERR_NOENT) { 02397 return err; 02398 } 02399 02400 if (err == LFS_ERR_NOENT) { 02401 break; 02402 } 02403 02404 if (!(0x80 & entry.d.type) && 02405 memcmp(&entry.d.u, e, sizeof(entry.d.u)) == 0) { 02406 return true; 02407 } 02408 } 02409 } 02410 02411 return false; 02412 } 02413 02414 static int lfs_relocate(lfs_t *lfs, 02415 const lfs_block_t oldpair[2], const lfs_block_t newpair[2]) { 02416 // find parent 02417 lfs_dir_t parent; 02418 lfs_entry_t entry; 02419 int res = lfs_parent(lfs, oldpair, &parent, &entry); 02420 if (res < 0) { 02421 return res; 02422 } 02423 02424 if (res) { 02425 // update disk, this creates a desync 02426 entry.d.u.dir[0] = newpair[0]; 02427 entry.d.u.dir[1] = newpair[1]; 02428 02429 int err = lfs_dir_update(lfs, &parent, &entry, NULL); 02430 if (err) { 02431 return err; 02432 } 02433 02434 // update internal root 02435 if (lfs_paircmp(oldpair, lfs->root) == 0) { 02436 LFS_DEBUG("Relocating root %" PRIu32 " %" PRIu32, 02437 newpair[0], newpair[1]); 02438 lfs->root[0] = newpair[0]; 02439 lfs->root[1] = newpair[1]; 02440 } 02441 02442 // clean up bad block, which should now be a desync 02443 return lfs_deorphan(lfs); 02444 } 02445 02446 // find pred 02447 res = lfs_pred(lfs, oldpair, &parent); 02448 if (res < 0) { 02449 return res; 02450 } 02451 02452 if (res) { 02453 // just replace bad pair, no desync can occur 02454 parent.d.tail[0] = newpair[0]; 02455 parent.d.tail[1] = newpair[1]; 02456 02457 return lfs_dir_commit(lfs, &parent, NULL, 0); 02458 } 02459 02460 // couldn't find dir, must be new 02461 return 0; 02462 } 02463 02464 int lfs_deorphan(lfs_t *lfs) { 02465 lfs->deorphaned = true; 02466 02467 if (lfs_pairisnull(lfs->root)) { 02468 return 0; 02469 } 02470 02471 lfs_dir_t pdir = {.d.size = 0x80000000}; 02472 lfs_dir_t cwd = {.d.tail[0] = 0, .d.tail[1] = 1}; 02473 02474 // iterate over all directory directory entries 02475 while (!lfs_pairisnull(cwd.d.tail)) { 02476 int err = lfs_dir_fetch(lfs, &cwd, cwd.d.tail); 02477 if (err) { 02478 return err; 02479 } 02480 02481 // check head blocks for orphans 02482 if (!(0x80000000 & pdir.d.size)) { 02483 // check if we have a parent 02484 lfs_dir_t parent; 02485 lfs_entry_t entry; 02486 int res = lfs_parent(lfs, pdir.d.tail, &parent, &entry); 02487 if (res < 0) { 02488 return res; 02489 } 02490 02491 if (!res) { 02492 // we are an orphan 02493 LFS_DEBUG("Found orphan %" PRIu32 " %" PRIu32, 02494 pdir.d.tail[0], pdir.d.tail[1]); 02495 02496 pdir.d.tail[0] = cwd.d.tail[0]; 02497 pdir.d.tail[1] = cwd.d.tail[1]; 02498 02499 err = lfs_dir_commit(lfs, &pdir, NULL, 0); 02500 if (err) { 02501 return err; 02502 } 02503 02504 break; 02505 } 02506 02507 if (!lfs_pairsync(entry.d.u.dir, pdir.d.tail)) { 02508 // we have desynced 02509 LFS_DEBUG("Found desync %" PRIu32 " %" PRIu32, 02510 entry.d.u.dir[0], entry.d.u.dir[1]); 02511 02512 pdir.d.tail[0] = entry.d.u.dir[0]; 02513 pdir.d.tail[1] = entry.d.u.dir[1]; 02514 02515 err = lfs_dir_commit(lfs, &pdir, NULL, 0); 02516 if (err) { 02517 return err; 02518 } 02519 02520 break; 02521 } 02522 } 02523 02524 // check entries for moves 02525 lfs_entry_t entry; 02526 while (true) { 02527 err = lfs_dir_next(lfs, &cwd, &entry); 02528 if (err && err != LFS_ERR_NOENT) { 02529 return err; 02530 } 02531 02532 if (err == LFS_ERR_NOENT) { 02533 break; 02534 } 02535 02536 // found moved entry 02537 if (entry.d.type & 0x80) { 02538 int moved = lfs_moved(lfs, &entry.d.u); 02539 if (moved < 0) { 02540 return moved; 02541 } 02542 02543 if (moved) { 02544 LFS_DEBUG("Found move %" PRIu32 " %" PRIu32, 02545 entry.d.u.dir[0], entry.d.u.dir[1]); 02546 err = lfs_dir_remove(lfs, &cwd, &entry); 02547 if (err) { 02548 return err; 02549 } 02550 } else { 02551 LFS_DEBUG("Found partial move %" PRIu32 " %" PRIu32, 02552 entry.d.u.dir[0], entry.d.u.dir[1]); 02553 entry.d.type &= ~0x80; 02554 err = lfs_dir_update(lfs, &cwd, &entry, NULL); 02555 if (err) { 02556 return err; 02557 } 02558 } 02559 } 02560 } 02561 02562 memcpy(&pdir, &cwd, sizeof(pdir)); 02563 } 02564 02565 return 0; 02566 }
Generated on Tue Aug 9 2022 00:37:09 by
1.7.2