1 /*
2 * Copyright (c) 2013 Heather Lee Wilson
3 *
4 * Use of this source code is governed by a MIT-style
5 * license that can be found in the LICENSE file or at
6 * https://opensource.org/licenses/MIT
7 */
8 #include <dev/flash_nor.h>
9 #include <lib/norfs.h>
10 #include <lib/norfs_inode.h>
11 #include <lib/norfs_config.h>
12 #include <iovec.h>
13 #include <stdlib.h>
14 #include <lk/err.h>
15 #include <string.h>
16 #include <platform.h>
17 #include <lib/cksum.h>
18 #include <platform/flash_nor_config.h>
19 #include <lk/list.h>
20 #include <lk/debug.h>
21
22 /* FRIEND_TEST non-static if unit testing, in order to
23 * allow functions to be exposed by a test header file.
24 */
25 #ifdef WITH_LIB_UNITTEST
26 #define FRIEND_TEST
27 #else
28 #define FRIEND_TEST static
29 #endif
30
31 #define member_size(type, member) sizeof(((type *)0)->member)
32
33
34 /* Handle rolling over of version field beyond max(uint16_t) by assuming that
35 * the difference between the smallest and largest versions are no more than
36 * half the range of uint16_t. By subtracting one unsigned uint16_t from
37 * another, then casting the delta to int16_t, if the delta is greater than
38 * 1/2 * max(uint16_t), then the most significant bit will be a 1, causing the
39 * signed integer to be negative and VERSION_GREATER_THAN to return false.
40 */
41 #define VERSION_GREATER_THAN(a, b) ((int16_t)((a) - (b)) > 0)
42
43 struct norfs_header {
44 uint32_t key;
45 uint16_t version;
46 uint16_t len;
47 uint8_t flags;
48 uint16_t crc;
49 };
50
51 /* Block header written after successful erase. */
52 FRIEND_TEST const unsigned char NORFS_BLOCK_HEADER[4] = {'T', 'O', 'F', 'U'};
53 /* Block header to indicate garbage collection has started. */
54 FRIEND_TEST const unsigned char NORFS_BLOCK_GC_STARTED_HEADER[2] = {'S', 'O'};
55 /* Block header to indicate block was not interrupted during garbage
56 * collection.
57 */
58 FRIEND_TEST const unsigned char NORFS_BLOCK_GC_FINISHED_HEADER[2] = {'U', 'P'};
59
60 FRIEND_TEST uint32_t write_pointer = 0;
61 FRIEND_TEST uint32_t total_remaining_space = NORFS_AVAILABLE_SPACE;
62 FRIEND_TEST uint8_t num_free_blocks = 0;
63 static bool fs_mounted = false;
64 FRIEND_TEST uint32_t norfs_nvram_offset;
65 static struct list_node inode_list;
66
67 static bool block_free[NORFS_NUM_BLOCKS];
68
69 static status_t collect_garbage(void);
70 static status_t load_and_verify_obj(uint32_t *ptr, struct norfs_header *header);
71
block_num(uint32_t flash_pointer)72 FRIEND_TEST uint8_t block_num(uint32_t flash_pointer) {
73 return flash_pointer/FLASH_PAGE_SIZE;
74 }
75
76 /* Update pointer to a free block. If no free blocks, return error. */
find_free_block(uint32_t * ptr)77 FRIEND_TEST status_t find_free_block(uint32_t *ptr) {
78 uint8_t i = block_num(*ptr) + 1;
79 uint8_t imod;
80 for (uint8_t j = 0; j < NORFS_NUM_BLOCKS; i++, j++) {
81 imod = i % NORFS_NUM_BLOCKS;
82 /* If is a free block, return. */
83 if (block_free[imod]) {
84 *ptr = imod * FLASH_PAGE_SIZE + sizeof(NORFS_BLOCK_HEADER);
85 return NO_ERROR;
86 }
87 }
88 /* A free block could not be found. */
89 return ERR_NO_MEMORY;
90 }
91
curr_block_free_space(uint32_t pointer)92 static uint32_t curr_block_free_space(uint32_t pointer) {
93 return (block_num(pointer) + 1) * FLASH_PAGE_SIZE - pointer;
94 }
95
block_full(uint8_t block,uint32_t ptr)96 static bool block_full(uint8_t block, uint32_t ptr) {
97 if (block != block_num(ptr)) {
98 return true;
99 }
100 return curr_block_free_space(ptr) < NORFS_OBJ_OFFSET;
101 }
102
select_garbage_block(uint32_t ptr)103 static uint8_t select_garbage_block(uint32_t ptr) {
104 return (block_num(ptr) + 1) % 8;
105 }
106
nvram_read(size_t offset,size_t length,void * ptr)107 static ssize_t nvram_read(size_t offset, size_t length, void *ptr) {
108 return flash_nor_read(NORFS_BANK, offset + norfs_nvram_offset, length, ptr);
109 }
110
nvram_write(size_t offset,size_t length,const void * ptr)111 static ssize_t nvram_write(size_t offset, size_t length, const void *ptr) {
112 return flash_nor_write(NORFS_BANK, offset + norfs_nvram_offset, length,
113 ptr);
114 }
115
nvram_erase_pages(size_t offset,size_t length)116 static ssize_t nvram_erase_pages(size_t offset, size_t length) {
117 return flash_nor_erase_pages(NORFS_BANK, offset + norfs_nvram_offset,
118 length);
119 }
120
nvram_flash_pointer(uint32_t loc)121 unsigned char *nvram_flash_pointer(uint32_t loc) {
122 return FLASH_PTR(flash_nor_get_bank(NORFS_BANK), loc + norfs_nvram_offset);
123 }
124
get_inode(uint32_t key,struct norfs_inode ** inode)125 FRIEND_TEST bool get_inode(uint32_t key, struct norfs_inode **inode) {
126 struct list_node *curr_lnode;
127 struct norfs_inode *curr_inode;
128 uint32_t curr_key;
129
130 if (!inode)
131 return false;
132
133 *inode = NULL;
134 list_for_every(&inode_list, curr_lnode) {
135 curr_inode = containerof(curr_lnode, struct norfs_inode, lnode);
136 nvram_read(curr_inode->location + NORFS_KEY_OFFSET,
137 sizeof(curr_key), &curr_key);
138 if (curr_key == key) {
139 *inode = curr_inode;
140 return true;
141 }
142 }
143 return false;
144 }
145
calculate_header_crc(uint32_t key,uint16_t version,uint16_t len,uint8_t flags)146 static uint16_t calculate_header_crc(uint32_t key, uint16_t version,
147 uint16_t len, uint8_t flags) {
148 uint16_t crc = crc16((unsigned char *) &key, sizeof(key));
149 crc = update_crc16(crc, (unsigned char *) &version, sizeof(version));
150 crc = update_crc16(crc, (unsigned char *) &len, sizeof(len));
151 crc = update_crc16(crc, (unsigned char *) &flags, sizeof(flags));
152 return crc;
153 }
154
155 /* Read header into parameter buffers. Return bytes written. */
read_header(uint32_t ptr,struct norfs_header * header)156 static ssize_t read_header(uint32_t ptr, struct norfs_header *header) {
157 ssize_t total_bytes_read = 0;
158 ssize_t bytes_read = 0;
159 bytes_read = nvram_read(ptr + NORFS_KEY_OFFSET,
160 sizeof(header->key), &header->key);
161 if (bytes_read < 0) {
162 return bytes_read;
163 }
164 total_bytes_read += bytes_read;
165 bytes_read = nvram_read(ptr + NORFS_VERSION_OFFSET,
166 sizeof(header->version), &header->version);
167 if (bytes_read < 0) {
168 return bytes_read;
169 }
170 total_bytes_read += bytes_read;
171 bytes_read = nvram_read(ptr + NORFS_LENGTH_OFFSET,
172 sizeof(header->len), &header->len);
173 if (bytes_read < 0) {
174 return bytes_read;
175 }
176 total_bytes_read += bytes_read;
177 bytes_read = nvram_read(ptr + NORFS_FLAGS_OFFSET,
178 sizeof(header->flags), &header->flags);
179 if (bytes_read < 0) {
180 return bytes_read;
181 }
182 total_bytes_read += bytes_read;
183
184 /* Increment pointer by one byte to account for unused padding. */
185 total_bytes_read += 1;
186 bytes_read = nvram_read(ptr + NORFS_CHECKSUM_OFFSET,
187 sizeof(header->crc), &header->crc);
188 if (bytes_read < 0) {
189 return bytes_read;
190 }
191 total_bytes_read += bytes_read;
192
193 return total_bytes_read;
194 }
195
norfs_read_obj_iovec(uint32_t key,iovec_t * obj_iov,uint32_t iov_count,size_t * bytes_read,uint8_t flags)196 status_t norfs_read_obj_iovec(uint32_t key, iovec_t *obj_iov,
197 uint32_t iov_count, size_t *bytes_read, uint8_t flags) {
198 if (!fs_mounted)
199 return ERR_NOT_MOUNTED;
200
201 uint32_t read_ptr;
202 uint16_t to_read, total_to_read;
203 struct norfs_inode *inode;
204 struct norfs_header stored_header;
205 int16_t bytes = 0;
206 uint8_t i = 0;
207 ssize_t iov_size = iovec_size(obj_iov, iov_count);
208
209 if (bytes_read) {
210 *bytes_read = 0;
211 }
212
213 if (!get_inode(key, &inode)) {
214 return ERR_NOT_FOUND;
215 }
216 read_ptr = inode->location;
217 bytes = read_header(read_ptr, &stored_header);
218
219 total_to_read = MIN(stored_header.len, iov_size);
220 if (bytes < 0) {
221 TRACEF("Error reading header. Status: %d\n", bytes);
222 return bytes;
223 }
224 read_ptr += bytes;
225
226 if (stored_header.flags & NORFS_DELETED_MASK) {
227 TRACEF("Object is already deleted.\n");
228 return ERR_NOT_FOUND;
229 }
230
231 while (*bytes_read < total_to_read) {
232 to_read = MIN(total_to_read - *bytes_read, obj_iov[i].iov_len);
233 bytes = nvram_read(read_ptr + *bytes_read,
234 to_read, obj_iov[i].iov_base);
235 if (bytes < 0) {
236 TRACEF("Read failed with error: %d\n", bytes);
237 return bytes;
238 }
239 if (bytes_read) {
240 *bytes_read += bytes;
241 }
242 i++;
243 }
244
245 return NO_ERROR;
246 }
247
write_obj_header(uint32_t * ptr,uint32_t key,uint16_t version,uint16_t len,uint8_t flags,uint16_t crc)248 static status_t write_obj_header(uint32_t *ptr, uint32_t key, uint16_t version,
249 uint16_t len, uint8_t flags, uint16_t crc) {
250 unsigned char buff[WORD_SIZE];
251 int bytes_written;
252
253 bytes_written = nvram_write(*ptr, sizeof(key), &key);
254 if (bytes_written < 0) {
255 return bytes_written;
256 }
257 *ptr += bytes_written;
258
259 memcpy(buff, &version, sizeof(version));
260 memcpy(buff + sizeof(version), &len, sizeof(len));
261 bytes_written = nvram_write(*ptr, sizeof(buff), &buff);
262 if (bytes_written < 0) {
263 return bytes_written;
264 }
265 *ptr += bytes_written;
266
267 memcpy(buff, &flags, sizeof(flags));
268 memset(buff + 1, 1, sizeof(flags));
269 memcpy(buff + 2, &crc, sizeof(crc));
270 bytes_written = nvram_write(*ptr, sizeof(buff), &buff);
271 if (bytes_written < 0) {
272 return bytes_written;
273 }
274 *ptr += bytes_written;
275 return NO_ERROR;
276 }
277
copy_iovec_to_disk(const struct iovec * iov,uint16_t iov_count,uint32_t * location,uint16_t * crc)278 static status_t copy_iovec_to_disk(const struct iovec *iov, uint16_t iov_count,
279 uint32_t *location, uint16_t *crc) {
280 unsigned char word[4] = {0};
281 uint16_t iov_ptr = 0;
282 uint16_t word_ptr = 0;
283 uint8_t word_size = sizeof(word);
284 int bytes_written;
285 for (uint16_t i = 0; i < iov_count; i++) {
286 while ((uint16_t)iov[i].iov_len - iov_ptr > word_size - word_ptr) {
287 memcpy(word + word_ptr,
288 (unsigned char *)iov[i].iov_base + iov_ptr, word_size -
289 word_ptr);
290 iov_ptr += word_size - word_ptr;
291
292 bytes_written = nvram_write(*location, sizeof(word),
293 &word);
294 if (bytes_written < 0) {
295 TRACEF("Error while writing: %d\n", bytes_written);
296 return bytes_written;
297 }
298
299 *location += bytes_written;
300 *crc = update_crc16(*crc, word, sizeof(word));
301 memset(word, 0, sizeof(word));
302 word_ptr = 0;
303 }
304
305 memcpy((unsigned char *)word + word_ptr,
306 (unsigned char *)iov[i].iov_base + iov_ptr,
307 iov[i].iov_len - iov_ptr);
308 word_ptr += iov[i].iov_len - iov_ptr;
309
310 iov_ptr = 0;
311 }
312
313 if (word_ptr > 0) {
314 bytes_written = nvram_write(*location, sizeof(word),
315 &word);
316
317 if (bytes_written < 0) {
318 TRACEF("Error writing: %d\n", bytes_written);
319 return bytes_written;
320 }
321
322 *location += bytes_written;
323 *crc = update_crc16(*crc, word, word_ptr);
324 }
325 return NO_ERROR;
326 }
327
initialize_next_block(uint32_t * ptr)328 static status_t initialize_next_block(uint32_t *ptr) {
329 uint32_t header_pointer;
330 ssize_t bytes_written;
331 status_t status;
332
333 /* Update write pointer. */
334 status = find_free_block(ptr);
335 if (status) {
336 TRACEF("Error finding free block. Status: %d\n", status);
337 return status;
338 }
339
340 num_free_blocks--;
341 block_free[block_num(*ptr)] = false;
342 bytes_written = nvram_write(*ptr,
343 sizeof(NORFS_BLOCK_GC_STARTED_HEADER), &NORFS_BLOCK_GC_STARTED_HEADER);
344
345 if (bytes_written < 0) {
346 TRACEF("Error writing header.\n");
347 return bytes_written;
348 }
349
350 header_pointer = *ptr + bytes_written;
351 *ptr += sizeof(NORFS_BLOCK_GC_STARTED_HEADER) +
352 sizeof(NORFS_BLOCK_GC_FINISHED_HEADER);
353
354 if (num_free_blocks < NORFS_MIN_FREE_BLOCKS) {
355 status = collect_garbage();
356 if (status) {
357 TRACEF("Failed to collection garbage. Error: %d\n.",
358 status);
359 return status;
360 }
361 }
362
363 status = nvram_write(header_pointer,
364 sizeof(NORFS_BLOCK_GC_FINISHED_HEADER),
365 &NORFS_BLOCK_GC_FINISHED_HEADER);
366 if (status < 0) {
367 TRACEF("Failed to write header.\n");
368 return status;
369 }
370
371 return NO_ERROR;
372 }
373
write_obj_iovec(const iovec_t * iov,uint iov_count,uint * location,uint32_t key,uint16_t version,uint8_t flags)374 status_t write_obj_iovec(const iovec_t *iov, uint iov_count, uint *location,
375 uint32_t key, uint16_t version, uint8_t flags) {
376 uint16_t crc = 0;
377 uint16_t len = iovec_size(iov, iov_count);
378 status_t status;
379
380 uint32_t header_loc = *location;
381 *location += NORFS_OBJ_OFFSET;
382 crc = calculate_header_crc(key, version, len, flags);
383
384 if (!(flags & NORFS_DELETED_MASK)) {
385 /* If object is not a deletion header, write object bytes to disk. */
386 status = copy_iovec_to_disk(iov, iov_count, location, &crc);
387 if (status) {
388 TRACEF("Error writing. Status: %d\n", status);
389 return status;
390 }
391 }
392
393 status = write_obj_header(&header_loc, key, version, len, flags, crc);
394 if (status) {
395 TRACEF("Error writing. Status: %d\n", status);
396 return status;
397 }
398
399 return NO_ERROR;
400 }
401
norfs_read_obj(uint32_t key,unsigned char * buffer,uint16_t buffer_len,size_t * bytes_read,uint8_t flags)402 status_t norfs_read_obj(uint32_t key, unsigned char *buffer,
403 uint16_t buffer_len, size_t *bytes_read,
404 uint8_t flags) {
405 if (!fs_mounted)
406 return ERR_NOT_MOUNTED;
407
408 struct iovec vec[1];
409 vec->iov_base = buffer;
410 vec->iov_len = buffer_len;
411 status_t status = norfs_read_obj_iovec(key, vec, 1, bytes_read, flags);
412
413 return status;
414 }
415
norfs_put_obj(uint32_t key,unsigned char * obj,uint16_t len,uint8_t flags)416 status_t norfs_put_obj(uint32_t key, unsigned char *obj, uint16_t len,
417 uint8_t flags) {
418 if (!fs_mounted)
419 return ERR_NOT_MOUNTED;
420
421 if (key == 0xFFFF) {
422 return ERR_INVALID_ARGS;
423 }
424 status_t status;
425 struct iovec const vec[1] = {{obj, len}};
426 status = norfs_put_obj_iovec(key, vec, 1, flags);
427 return status;
428 }
429
is_deleted(uint32_t loc)430 bool is_deleted(uint32_t loc) {
431 uint8_t flags;
432 nvram_read(loc + NORFS_FLAGS_OFFSET, sizeof(flags), &flags);
433 return NORFS_DELETED_MASK & flags;
434 }
435
norfs_remove_obj(uint32_t key)436 status_t norfs_remove_obj(uint32_t key) {
437 if (!fs_mounted)
438 return ERR_NOT_MOUNTED;
439
440 struct norfs_inode *inode;
441 uint16_t prior_len;
442 struct iovec iov[1];
443 status_t status;
444 bool success = get_inode(key, &inode);
445 if (!success || is_deleted(inode->location))
446 return ERR_NOT_FOUND;
447
448 status = nvram_read(inode->location + NORFS_LENGTH_OFFSET,
449 sizeof(uint16_t), &prior_len);
450 if (status < 0) {
451 TRACEF("Failed to read during norfs_remove_obj. Status: %d\n", status);
452 return status;
453 }
454
455 iov->iov_base = NULL;
456 iov->iov_len = 0;
457
458 /*
459 * Write a deleted object by passing a null iovec pointer. Only header
460 * will be written.
461 */
462 status = norfs_put_obj_iovec(key, iov, 0, NORFS_DELETED_MASK);
463 if (status)
464 TRACEF("Error putting object. %d\n", status);
465
466 return status;
467 }
468
find_space_for_object(uint16_t obj_len,uint32_t * ptr)469 static status_t find_space_for_object(uint16_t obj_len, uint32_t *ptr) {
470 status_t status;
471 uint8_t initial_block_num = block_num(*ptr);
472 while (curr_block_free_space(*ptr) < (uint16_t) NORFS_FLASH_SIZE(obj_len)) {
473 status = initialize_next_block(ptr);
474 if (status)
475 return status;
476 /* If we have already tried and failed to write to this block, exit. */
477 if (block_num(*ptr) == initial_block_num)
478 return ERR_NO_MEMORY;
479 }
480 return NO_ERROR;
481 }
482
483 /*
484 * Store an object in flash. Moves write_pointer to new block and garbage
485 * collects if needed. If write fails, will reattempt.
486 * How to handle write failures is not fully defined - at the moment I stop once
487 * find_free_block is attempting to rewrite to a block it has already failed to
488 * write to - after a full loop in a round-robin style garbage selection of
489 * blocks. Which is a lot of write attempts.
490 */
norfs_put_obj_iovec(uint32_t key,const iovec_t * iov,uint32_t iov_count,uint8_t flags)491 status_t norfs_put_obj_iovec(uint32_t key, const iovec_t *iov,
492 uint32_t iov_count, uint8_t flags) {
493 if (!fs_mounted)
494 return ERR_NOT_MOUNTED;
495
496 if (key == 0xFFFF) {
497 return ERR_INVALID_ARGS;
498 }
499
500 uint8_t block_num_to_write;
501 struct norfs_inode *inode;
502 uint16_t len = iovec_size(iov, iov_count);
503 status_t status;
504 uint8_t stored_flags;
505 uint16_t version = 0;
506 uint32_t header_loc;
507 bool deletion = flags & NORFS_DELETED_MASK;
508 bool obj_preexists = get_inode(key, &inode);
509 if (obj_preexists) {
510 nvram_read(inode->location + NORFS_FLAGS_OFFSET,
511 sizeof(stored_flags), &stored_flags);
512 if (stored_flags & flags & NORFS_DELETED_MASK) {
513 /* Attempting to delete an object no longer in filesystem. */
514 TRACEF("The object attempting to be removed has already been \
515 deleted. stored_flags: 0x%x\n", stored_flags);
516 return ERR_NOT_FOUND;
517 }
518
519 nvram_read(inode->location + NORFS_VERSION_OFFSET,
520 sizeof(version), &version);
521 version++;
522 } else if (deletion) {
523 /* Attempting to delete a non-existent object. */
524 TRACEF("Attempting to remove an object not in filesystem.\n");
525 return ERR_NOT_FOUND;
526 } else {
527 inode = malloc(sizeof(struct norfs_inode));
528 inode->reference_count = 1;
529 }
530
531 flash_nor_begin(NORFS_BANK);
532
533 if (NORFS_FLASH_SIZE(len) > NORFS_MAX_OBJ_LEN) {
534 TRACEF("Object too big. Not adding.\n");
535 flash_nor_end(NORFS_BANK);
536 return ERR_TOO_BIG;
537 }
538
539 if (!deletion && (NORFS_FLASH_SIZE(len) > total_remaining_space)) {
540 TRACEF("Not enough remaining space. Remaining space: %d\tObject len: \
541 %d\n", total_remaining_space, len);
542 flash_nor_end(NORFS_BANK);
543 return ERR_NO_MEMORY;
544 }
545
546 status = find_space_for_object(len, &write_pointer);
547 if (status) {
548 TRACEF("Error finding space for object. Status: %d\n", status);
549 flash_nor_end(NORFS_BANK);
550 return ERR_IO;
551 }
552
553 block_num_to_write = block_num(write_pointer);
554 header_loc = write_pointer;
555 status = write_obj_iovec(iov, iov_count, &write_pointer, key,
556 version, flags);
557 if (!status) {
558 if (!obj_preexists) {
559 list_add_tail(&inode_list, &inode->lnode);
560 } else {
561 /* If object preexists, remove outdated version from remaining space. */
562 uint16_t prior_len;
563 nvram_read(inode->location + NORFS_LENGTH_OFFSET,
564 sizeof(uint16_t), &prior_len);
565 total_remaining_space += NORFS_FLASH_SIZE(prior_len);
566 inode->reference_count++;
567 }
568 inode->location = header_loc;
569 total_remaining_space -= NORFS_FLASH_SIZE(len);
570 } else {
571 TRACEF("Error writing object. Status: %d\n", status);
572 }
573
574 /* If write error, or if fell off block, find new block. */
575 if (status < 0 || block_num(write_pointer) != block_num_to_write) {
576 initialize_next_block(&write_pointer);
577 }
578
579 flash_nor_end(NORFS_BANK);
580 return status;
581 }
582
remove_inode(struct norfs_inode * inode)583 static void remove_inode(struct norfs_inode *inode) {
584 if (!inode)
585 return;
586 list_delete(&inode->lnode);
587 free(inode);
588 inode = NULL;
589 }
590
591 /* Verifies objects, and copies to new block if it is the latest version. */
collect_garbage_object(uint32_t * garbage_read_pointer,uint32_t * garbage_write_pointer)592 static status_t collect_garbage_object(uint32_t *garbage_read_pointer,
593 uint32_t *garbage_write_pointer) {
594 struct norfs_inode *inode;
595 struct norfs_header header;
596 bool inode_found;
597 status_t status;
598 struct iovec iov[1];
599 uint32_t new_obj_loc;
600 uint32_t garb_obj_loc = *garbage_read_pointer;
601 status = load_and_verify_obj(garbage_read_pointer, &header);
602 if (status) {
603 TRACEF("Failed to load garbage_obj at %d\n", *garbage_read_pointer);
604 return status;
605 }
606 inode_found = get_inode(header.key, &inode);
607 if (inode_found) {
608 if (garb_obj_loc == inode->location) {
609 /* Object in garbage block is latest version. */
610 if (header.flags & NORFS_DELETED_MASK && (inode->reference_count == 1)) {
611 /* If last version of object, remove. */
612 remove_inode(inode);
613 total_remaining_space += NORFS_OBJ_OFFSET;
614 return NO_ERROR;
615 }
616 iov->iov_base = nvram_flash_pointer(garb_obj_loc + NORFS_OBJ_OFFSET);
617 iov->iov_len = header.len;
618 new_obj_loc = *garbage_write_pointer;
619 status = write_obj_iovec(iov, 1, garbage_write_pointer, header.key,
620 header.version + 1, header.flags);
621 if (status) {
622 TRACEF("Failed to copy garbage object. Status: %d\n", status);
623 return status;
624 }
625 inode->location = new_obj_loc;
626 return NO_ERROR;
627 } else {
628 inode->reference_count--;
629 return NO_ERROR;
630 }
631 }
632
633 if (is_deleted(*garbage_read_pointer)) {
634 return NO_ERROR;
635 }
636 return ERR_NOT_FOUND;
637 }
638
erase_block(uint8_t block)639 static status_t erase_block(uint8_t block) {
640 ssize_t bytes_erased;
641 ssize_t bytes_written;
642 status_t status;
643 uint32_t loc = block * FLASH_PAGE_SIZE;
644
645 /* Block must fall within range of actual number of NVRAM blocks. */
646 if (block > NORFS_NUM_BLOCKS) {
647 TRACEF("Invalid block number: %d.\n", block);
648 return ERR_INVALID_ARGS;
649 }
650 status = flash_nor_begin(NORFS_BANK);
651 if (status) {
652 flash_nor_end(NORFS_BANK);
653 return status;
654 }
655
656 bytes_erased = nvram_erase_pages(loc, FLASH_PAGE_SIZE);
657 if (bytes_erased != FLASH_PAGE_SIZE) {
658 flash_nor_end(NORFS_BANK);
659 TRACEF("Did not erase exactly one flash page. Something went \
660 wrong.\n");
661 return ERR_IO;
662 }
663
664 bytes_written = nvram_write(loc, sizeof(NORFS_BLOCK_HEADER),
665 &NORFS_BLOCK_HEADER);
666
667 flash_nor_end(NORFS_BANK);
668 if (bytes_written < 0) {
669 TRACEF("Error during nvram_write. Status: %d\n", bytes_written);
670 return bytes_written;
671 }
672 block_free[block] = true;
673 num_free_blocks++;
674
675 return NO_ERROR;
676 }
677
collect_block(uint32_t garbage_block,uint32_t * garbage_write_ptr)678 FRIEND_TEST status_t collect_block(uint32_t garbage_block,
679 uint32_t *garbage_write_ptr) {
680 status_t status;
681 uint32_t garbage_read_ptr = garbage_block * FLASH_PAGE_SIZE +
682 NORFS_BLOCK_HEADER_SIZE;
683
684 while (!(block_full(garbage_block, garbage_read_ptr))) {
685 status = collect_garbage_object(&garbage_read_ptr, garbage_write_ptr);
686 if (status) {
687 break;
688 }
689 }
690 return erase_block(garbage_block);
691 }
692
collect_garbage(void)693 static status_t collect_garbage(void) {
694 status_t status;
695 uint8_t garbage_read_block = select_garbage_block(write_pointer);
696 status = collect_block(garbage_read_block, &write_pointer);
697
698 return status;
699 }
700
701 /*
702 * Load object into buffer and verify object's integrity via crc. ptr parameter
703 * is updated upon successful verification.
704 */
load_and_verify_obj(uint32_t * ptr,struct norfs_header * header)705 static status_t load_and_verify_obj(uint32_t *ptr, struct norfs_header *header) {
706 uint16_t calculated_crc;
707 ssize_t bytes;
708 ssize_t total_bytes_read = 0;
709 bytes = read_header(*ptr, header);
710 unsigned char *obj_ptr;
711
712 if (bytes < 0) {
713 TRACEF("Reading header failed at location: %d. Err: %d.\n", *ptr, bytes);
714 return bytes;
715 }
716
717 total_bytes_read += bytes;
718
719 /* If object is longer than the remaining space in current block, fail.
720 * When attempting to verify unwritten file space, will fail here. */
721 if (block_num(*ptr + header->len - 1) != block_num(*ptr)) {
722 return ERR_IO;
723 }
724
725 calculated_crc = calculate_header_crc(header->key, header->version,
726 header->len, header->flags);
727
728
729 obj_ptr = nvram_flash_pointer(*ptr + total_bytes_read);
730 calculated_crc = update_crc16(calculated_crc, obj_ptr, header->len);
731
732 total_bytes_read += header->len;
733 if (calculated_crc != header->crc) {
734 TRACEF("CRC check failed. Calculated: 0x%x\tActual: 0x%x\n",
735 calculated_crc, header->crc);
736 return ERR_CRC_FAIL;
737 }
738 *ptr += total_bytes_read;
739 *ptr = ROUNDUP(*ptr, WORD_SIZE);
740 return NO_ERROR;
741 }
742
read_block_verification(uint32_t * ptr)743 status_t read_block_verification(uint32_t *ptr) {
744 unsigned char block_header[sizeof(NORFS_BLOCK_HEADER) +
745 sizeof(NORFS_BLOCK_GC_STARTED_HEADER) +
746 sizeof(NORFS_BLOCK_GC_FINISHED_HEADER)];
747 int bytes_read = nvram_read(*ptr, sizeof(block_header),
748 block_header);
749
750 if (bytes_read < 0) {
751 TRACEF("Error reading while verifying block. Location: %d\n", *ptr);
752 return ERR_BAD_STATE;
753 }
754
755 for (uint8_t i = 0; i < sizeof(NORFS_BLOCK_HEADER); i++) {
756 if (block_header[i] != *(NORFS_BLOCK_HEADER + i)) {
757 return ERR_BAD_STATE;
758 }
759 }
760
761 bool valid_free_block = true;
762 for (uint8_t i = sizeof(NORFS_BLOCK_HEADER);
763 i < sizeof(NORFS_BLOCK_HEADER) +
764 sizeof(NORFS_BLOCK_GC_STARTED_HEADER) +
765 sizeof(NORFS_BLOCK_GC_FINISHED_HEADER);
766 i++) {
767 valid_free_block = valid_free_block && (block_header[i] == 0xFF);
768 }
769
770 /* This block has been successfully erased but has not been written to. */
771 if (valid_free_block) {
772 return ERR_NOT_CONFIGURED;
773 }
774
775 if (block_header[4] != NORFS_BLOCK_GC_STARTED_HEADER[0] ||
776 block_header[5] != NORFS_BLOCK_GC_STARTED_HEADER[1] ||
777 block_header[6] != NORFS_BLOCK_GC_FINISHED_HEADER[0] ||
778 block_header[7] != NORFS_BLOCK_GC_FINISHED_HEADER[1]) {
779 TRACEF("Garbage collection header invalid.\n");
780 return ERR_BAD_STATE;
781 }
782
783 *ptr += bytes_read;
784 return NO_ERROR;
785 }
786
mount_next_obj(void)787 static status_t mount_next_obj(void) {
788 uint16_t curr_obj_loc;
789 uint16_t inode_version, inode_len;
790 curr_obj_loc = write_pointer;
791 struct norfs_inode *inode;
792 struct norfs_header header;
793 status_t status;
794
795 status = load_and_verify_obj(&write_pointer, &header);
796 if (status) {
797 return status;
798 }
799 if (get_inode(header.key, &inode)) {
800 nvram_read(inode->location + NORFS_VERSION_OFFSET,
801 sizeof(inode_version), &inode_version);
802 if (VERSION_GREATER_THAN(header.version, inode_version)) {
803 /* This is a newer version of object than the version
804 currently being linked to in the inode. */
805 nvram_read(inode->location + NORFS_LENGTH_OFFSET,
806 sizeof(inode_len), &inode_len);
807 total_remaining_space += inode_len;
808 total_remaining_space -= header.len;
809 inode->location = curr_obj_loc;
810 }
811 inode->reference_count += 1;
812 } else {
813 /* Object not yet held in memory. Create new inode. */
814 inode = malloc(sizeof(struct norfs_inode));
815 inode->location = curr_obj_loc;
816
817 inode->reference_count = 1;
818
819 list_add_tail(&inode_list, &inode->lnode);
820 total_remaining_space -= NORFS_FLASH_SIZE(header.len);
821 }
822
823 return NO_ERROR;
824 }
825
826 /*
827 * Inodes for deleted objects need to be maintained during mounting, in case
828 * references show up in later blocks. However, these references need to be
829 * pruned prior to usage.
830 */
purge_unreferenced_inodes(void)831 static void purge_unreferenced_inodes(void) {
832 struct list_node *curr_lnode, *temp_node;
833 struct norfs_inode *curr_inode;
834 list_for_every_safe(&inode_list, curr_lnode, temp_node) {
835 curr_inode = containerof(curr_lnode, struct norfs_inode, lnode);
836 if (curr_inode->reference_count == 0) {
837 remove_inode(curr_inode);
838 }
839 }
840 }
841
norfs_mount_fs(uint32_t offset)842 status_t norfs_mount_fs(uint32_t offset) {
843 if (fs_mounted) {
844 TRACEF("Filesystem already mounted.\n");
845 return ERR_ALREADY_MOUNTED;
846 }
847 status_t status = 0;
848 norfs_nvram_offset = offset;
849
850 list_initialize(&inode_list);
851 flash_nor_begin(NORFS_BANK);
852 srand(current_time());
853
854 total_remaining_space = NORFS_AVAILABLE_SPACE;
855 num_free_blocks = 0;
856 TRACEF("Mounting NOR file system.\n");
857 for (uint8_t i = 0; i < NORFS_NUM_BLOCKS; i++) {
858 write_pointer = i * FLASH_PAGE_SIZE;
859 status = read_block_verification(&write_pointer);
860 if (status == ERR_BAD_STATE) {
861 erase_block(i);
862 continue;
863 } else if (status == ERR_NOT_CONFIGURED) {
864 /* Valid empty block. */
865 block_free[i] = true;
866 num_free_blocks++;
867 continue;
868 } else if (status != NO_ERROR) {
869 TRACEF("Unexpected status: %d. Exiting.\n", status);
870 flash_nor_end(NORFS_BANK);
871 return status;
872 }
873 block_free[i] = false;
874 while (!block_full(i, write_pointer)) {
875 status = mount_next_obj();
876 if (status)
877 break;
878 }
879 }
880
881 purge_unreferenced_inodes();
882
883 write_pointer = rand() % NORFS_NVRAM_SIZE;
884 status = initialize_next_block(&write_pointer);
885 if (status) {
886 TRACEF("Failed to find free block after mount.\n");
887 flash_nor_end(NORFS_BANK);
888 return status;
889 }
890
891 TRACEF("NOR filesystem successfully mounted.\n");
892 flash_nor_end(NORFS_BANK);
893 fs_mounted = true;
894 return NO_ERROR;
895 }
896
norfs_unmount_fs(void)897 void norfs_unmount_fs(void) {
898 TRACEF("Unmounting NOR file system\n");
899 struct list_node *curr_lnode;
900 struct norfs_inode *curr_inode;
901 struct list_node *temp_node;
902
903 if (!fs_mounted) {
904 TRACEF("Filesystem not mounted.\n");
905 return;
906 }
907 if (!list_is_empty(&inode_list)) {
908 list_for_every_safe(&inode_list, curr_lnode, temp_node) {
909 if (curr_lnode) {
910 curr_inode = containerof(curr_lnode, struct norfs_inode, lnode);
911 remove_inode(curr_inode);
912 }
913 }
914 }
915 write_pointer = rand() % NORFS_NVRAM_SIZE;
916 total_remaining_space = NORFS_AVAILABLE_SPACE;
917 num_free_blocks = 0;
918 for (uint8_t i = 0; i < NORFS_NUM_BLOCKS; i++) {
919 block_free[i] = false;
920 }
921 fs_mounted = false;
922 }
923
norfs_wipe_fs(void)924 void norfs_wipe_fs(void) {
925 norfs_unmount_fs();
926 flash_nor_begin(0);
927 nvram_erase_pages(0, 8 * FLASH_PAGE_SIZE);
928 flash_nor_end(0);
929 norfs_mount_fs(norfs_nvram_offset);
930 }
931