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