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