You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

563 lines
17KB

  1. /*
  2. * This file is part of the TREZOR project, https://trezor.io/
  3. *
  4. * Copyright (c) SatoshiLabs
  5. *
  6. * This program is free software: you can redistribute it and/or modify
  7. * it under the terms of the GNU General Public License as published by
  8. * the Free Software Foundation, either version 3 of the License, or
  9. * (at your option) any later version.
  10. *
  11. * This program is distributed in the hope that it will be useful,
  12. * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13. * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  14. * GNU General Public License for more details.
  15. *
  16. * You should have received a copy of the GNU General Public License
  17. * along with this program. If not, see <http://www.gnu.org/licenses/>.
  18. */
  19. #include <string.h>
  20. #include "norcow.h"
  21. #include "flash.h"
  22. #include "common.h"
  23. // NRC2 = 4e524332
  24. #define NORCOW_MAGIC ((uint32_t)0x3243524e)
  25. // NRCW = 4e524357
  26. #define NORCOW_MAGIC_V0 ((uint32_t)0x5743524e)
  27. #define NORCOW_WORD_SIZE (sizeof(uint32_t))
  28. #define NORCOW_PREFIX_LEN NORCOW_WORD_SIZE
  29. #define NORCOW_MAGIC_LEN NORCOW_WORD_SIZE
  30. #define NORCOW_VERSION_LEN NORCOW_WORD_SIZE
  31. // The key value which is used to indicate that the entry is not set.
  32. #define NORCOW_KEY_FREE (0xFFFF)
  33. // The key value which is used to indicate that the entry has been deleted.
  34. #define NORCOW_KEY_DELETED (0x0000)
  35. // The offset from the beginning of the sector where stored items start.
  36. #define NORCOW_STORAGE_START (NORCOW_HEADER_LEN + NORCOW_MAGIC_LEN + NORCOW_VERSION_LEN)
  37. // Map from sector index to sector number.
  38. static const uint8_t norcow_sectors[NORCOW_SECTOR_COUNT] = NORCOW_SECTORS;
  39. // The index of the active reading sector and writing sector. These should be equal except when storage version upgrade or compaction is in progress.
  40. static uint8_t norcow_active_sector = 0;
  41. static uint8_t norcow_write_sector = 0;
  42. // The norcow version of the reading sector.
  43. static uint32_t norcow_active_version = 0;
  44. // The offset of the first free item in the writing sector.
  45. static uint32_t norcow_free_offset = 0;
  46. /*
  47. * Returns pointer to sector, starting with offset
  48. * Fails when there is not enough space for data of given size
  49. */
  50. static const void *norcow_ptr(uint8_t sector, uint32_t offset, uint32_t size)
  51. {
  52. ensure(sectrue * (sector <= NORCOW_SECTOR_COUNT), "invalid sector");
  53. return flash_get_address(norcow_sectors[sector], offset, size);
  54. }
  55. /*
  56. * Writes data to given sector, starting from offset
  57. */
  58. static secbool norcow_write(uint8_t sector, uint32_t offset, uint32_t prefix, const uint8_t *data, uint16_t len)
  59. {
  60. if (sector >= NORCOW_SECTOR_COUNT) {
  61. return secfalse;
  62. }
  63. if (offset + NORCOW_PREFIX_LEN + len > NORCOW_SECTOR_SIZE) {
  64. return secfalse;
  65. }
  66. ensure(flash_unlock_write(), NULL);
  67. // write prefix
  68. ensure(flash_write_word(norcow_sectors[sector], offset, prefix), NULL);
  69. offset += NORCOW_PREFIX_LEN;
  70. if (data != NULL) {
  71. // write data
  72. for (uint16_t i = 0; i < len; i++, offset++) {
  73. ensure(flash_write_byte(norcow_sectors[sector], offset, data[i]), NULL);
  74. }
  75. } else {
  76. offset += len;
  77. }
  78. // pad with zeroes
  79. for (; offset % NORCOW_WORD_SIZE; offset++) {
  80. ensure(flash_write_byte(norcow_sectors[sector], offset, 0x00), NULL);
  81. }
  82. ensure(flash_lock_write(), NULL);
  83. return sectrue;
  84. }
  85. /*
  86. * Erases sector (and sets a magic)
  87. */
  88. static void erase_sector(uint8_t sector, secbool set_magic)
  89. {
  90. #if NORCOW_HEADER_LEN > 0
  91. // Backup the sector header.
  92. uint32_t header_backup[NORCOW_HEADER_LEN/sizeof(uint32_t)];
  93. const void *sector_start = norcow_ptr(sector, 0, NORCOW_HEADER_LEN);
  94. memcpy(header_backup, sector_start, sizeof(header_backup));
  95. #endif
  96. ensure(flash_erase(norcow_sectors[sector]), "erase failed");
  97. #if NORCOW_HEADER_LEN > 0
  98. // Copy the sector header back.
  99. ensure(flash_unlock_write(), NULL);
  100. for (uint32_t i = 0; i < NORCOW_HEADER_LEN/sizeof(uint32_t); ++i) {
  101. ensure(flash_write_word(norcow_sectors[sector], i*sizeof(uint32_t), header_backup[i]), NULL);
  102. }
  103. ensure(flash_lock_write(), NULL);
  104. #endif
  105. if (sectrue == set_magic) {
  106. ensure(norcow_write(sector, NORCOW_HEADER_LEN, NORCOW_MAGIC, NULL, 0), "set magic failed");
  107. ensure(norcow_write(sector, NORCOW_HEADER_LEN + NORCOW_MAGIC_LEN, ~NORCOW_VERSION, NULL, 0), "set version failed");
  108. }
  109. }
  110. #define ALIGN4(X) (X) = ((X) + 3) & ~3
  111. /*
  112. * Reads one item starting from offset
  113. */
  114. static secbool read_item(uint8_t sector, uint32_t offset, uint16_t *key, const void **val, uint16_t *len, uint32_t *pos)
  115. {
  116. *pos = offset;
  117. const void *k = norcow_ptr(sector, *pos, 2);
  118. if (k == NULL) return secfalse;
  119. *pos += 2;
  120. memcpy(key, k, sizeof(uint16_t));
  121. if (*key == NORCOW_KEY_FREE) {
  122. return secfalse;
  123. }
  124. const void *l = norcow_ptr(sector, *pos, 2);
  125. if (l == NULL) return secfalse;
  126. *pos += 2;
  127. memcpy(len, l, sizeof(uint16_t));
  128. *val = norcow_ptr(sector, *pos, *len);
  129. if (*val == NULL) return secfalse;
  130. *pos += *len;
  131. ALIGN4(*pos);
  132. return sectrue;
  133. }
  134. /*
  135. * Writes one item starting from offset
  136. */
  137. static secbool write_item(uint8_t sector, uint32_t offset, uint16_t key, const void *val, uint16_t len, uint32_t *pos)
  138. {
  139. uint32_t prefix = ((uint32_t)len << 16) | key;
  140. *pos = offset + NORCOW_PREFIX_LEN + len;
  141. ALIGN4(*pos);
  142. return norcow_write(sector, offset, prefix, val, len);
  143. }
  144. /*
  145. * Finds the offset from the beginning of the sector where stored items start.
  146. */
  147. static secbool find_start_offset(uint8_t sector, uint32_t *offset, uint32_t *version)
  148. {
  149. const uint32_t *magic = norcow_ptr(sector, NORCOW_HEADER_LEN, NORCOW_MAGIC_LEN + NORCOW_VERSION_LEN);
  150. if (magic == NULL) {
  151. return secfalse;
  152. }
  153. if (*magic == NORCOW_MAGIC) {
  154. *offset = NORCOW_STORAGE_START;
  155. *version = ~(magic[1]);
  156. } else if (*magic == NORCOW_MAGIC_V0) {
  157. *offset = NORCOW_HEADER_LEN + NORCOW_MAGIC_LEN;
  158. *version = 0;
  159. } else {
  160. return secfalse;
  161. }
  162. return sectrue;
  163. }
  164. /*
  165. * Finds item in given sector
  166. */
  167. static secbool find_item(uint8_t sector, uint16_t key, const void **val, uint16_t *len)
  168. {
  169. *val = NULL;
  170. *len = 0;
  171. uint32_t offset;
  172. uint32_t version;
  173. if (sectrue != find_start_offset(sector, &offset, &version)) {
  174. return secfalse;
  175. }
  176. for (;;) {
  177. uint16_t k, l;
  178. const void *v;
  179. uint32_t pos;
  180. if (sectrue != read_item(sector, offset, &k, &v, &l, &pos)) {
  181. break;
  182. }
  183. if (key == k) {
  184. *val = v;
  185. *len = l;
  186. }
  187. offset = pos;
  188. }
  189. return sectrue * (*val != NULL);
  190. }
  191. /*
  192. * Finds first unused offset in given sector
  193. */
  194. static uint32_t find_free_offset(uint8_t sector)
  195. {
  196. uint32_t offset;
  197. uint32_t version;
  198. if (sectrue != find_start_offset(sector, &offset, &version)) {
  199. return secfalse;
  200. }
  201. for (;;) {
  202. uint16_t key, len;
  203. const void *val;
  204. uint32_t pos;
  205. if (sectrue != read_item(sector, offset, &key, &val, &len, &pos)) {
  206. break;
  207. }
  208. offset = pos;
  209. }
  210. return offset;
  211. }
  212. /*
  213. * Compacts active sector and sets new active sector
  214. */
  215. static void compact(void)
  216. {
  217. uint32_t offsetr;
  218. uint32_t version;
  219. if (sectrue != find_start_offset(norcow_active_sector, &offsetr, &version)) {
  220. return;
  221. }
  222. norcow_write_sector = (norcow_active_sector + 1) % NORCOW_SECTOR_COUNT;
  223. erase_sector(norcow_write_sector, sectrue);
  224. uint32_t offsetw = NORCOW_STORAGE_START;
  225. for (;;) {
  226. // read item
  227. uint16_t k, l;
  228. const void *v;
  229. uint32_t posr;
  230. secbool r = read_item(norcow_active_sector, offsetr, &k, &v, &l, &posr);
  231. if (sectrue != r) {
  232. break;
  233. }
  234. offsetr = posr;
  235. // skip deleted items
  236. if (k == NORCOW_KEY_DELETED) {
  237. continue;
  238. }
  239. // copy the item
  240. uint32_t posw;
  241. ensure(write_item(norcow_write_sector, offsetw, k, v, l, &posw), "compaction write failed");
  242. offsetw = posw;
  243. }
  244. erase_sector(norcow_active_sector, secfalse);
  245. norcow_active_sector = norcow_write_sector;
  246. norcow_active_version = NORCOW_VERSION;
  247. norcow_free_offset = find_free_offset(norcow_write_sector);
  248. }
  249. /*
  250. * Initializes storage
  251. */
  252. void norcow_init(uint32_t *norcow_version)
  253. {
  254. flash_init();
  255. secbool found = secfalse;
  256. *norcow_version = 0;
  257. // detect active sector - starts with magic and has highest version
  258. for (uint8_t i = 0; i < NORCOW_SECTOR_COUNT; i++) {
  259. uint32_t offset;
  260. if (sectrue == find_start_offset(i, &offset, &norcow_active_version) && norcow_active_version >= *norcow_version) {
  261. found = sectrue;
  262. norcow_active_sector = i;
  263. *norcow_version = norcow_active_version;
  264. }
  265. }
  266. // If no active sectors found or version downgrade, then erase.
  267. if (sectrue != found || *norcow_version > NORCOW_VERSION) {
  268. norcow_wipe();
  269. *norcow_version = NORCOW_VERSION;
  270. } else if (*norcow_version < NORCOW_VERSION) {
  271. // Prepare write sector for storage upgrade.
  272. norcow_write_sector = (norcow_active_sector + 1) % NORCOW_SECTOR_COUNT;
  273. erase_sector(norcow_write_sector, sectrue);
  274. norcow_free_offset = find_free_offset(norcow_write_sector);
  275. } else {
  276. norcow_write_sector = norcow_active_sector;
  277. norcow_free_offset = find_free_offset(norcow_write_sector);
  278. }
  279. }
  280. /*
  281. * Wipe the storage
  282. */
  283. void norcow_wipe(void)
  284. {
  285. erase_sector(0, sectrue);
  286. for (uint8_t i = 1; i < NORCOW_SECTOR_COUNT; i++) {
  287. erase_sector(i, secfalse);
  288. }
  289. norcow_active_sector = 0;
  290. norcow_active_version = NORCOW_VERSION;
  291. norcow_write_sector = 0;
  292. norcow_free_offset = NORCOW_STORAGE_START;
  293. }
  294. /*
  295. * Looks for the given key, returns status of the operation
  296. */
  297. secbool norcow_get(uint16_t key, const void **val, uint16_t *len)
  298. {
  299. return find_item(norcow_active_sector, key, val, len);
  300. }
  301. /*
  302. * Reads the next entry in the storage starting at offset. Returns secfalse if there is none.
  303. */
  304. secbool norcow_get_next(uint32_t *offset, uint16_t *key, const void **val, uint16_t *len)
  305. {
  306. if (*offset == 0) {
  307. uint32_t version;
  308. if (sectrue != find_start_offset(norcow_active_sector, offset, &version)) {
  309. return secfalse;
  310. }
  311. }
  312. for (;;) {
  313. uint32_t pos = 0;
  314. secbool ret = read_item(norcow_active_sector, *offset, key, val, len, &pos);
  315. if (sectrue != ret) {
  316. break;
  317. }
  318. *offset = pos;
  319. // Skip deleted items.
  320. if (*key == NORCOW_KEY_DELETED) {
  321. continue;
  322. }
  323. if (norcow_active_version == 0) {
  324. // Check whether the item is the latest instance.
  325. uint32_t offsetr = *offset;
  326. for (;;) {
  327. uint16_t k;
  328. uint16_t l;
  329. const void *v;
  330. ret = read_item(norcow_active_sector, offsetr, &k, &v, &l, &offsetr);
  331. if (sectrue != ret) {
  332. // There is no newer instance of the item.
  333. return sectrue;
  334. }
  335. if (*key == k) {
  336. // There exists a newer instance of the item.
  337. break;
  338. }
  339. }
  340. } else {
  341. return sectrue;
  342. }
  343. }
  344. return secfalse;
  345. }
  346. /*
  347. * Sets the given key, returns status of the operation. If NULL is passed
  348. * as val, then norcow_set allocates a new key of size len. The value should
  349. * then be written using norcow_update_bytes().
  350. */
  351. secbool norcow_set(uint16_t key, const void *val, uint16_t len)
  352. {
  353. secbool found;
  354. return norcow_set_ex(key, val, len, &found);
  355. }
  356. secbool norcow_set_ex(uint16_t key, const void *val, uint16_t len, secbool *found)
  357. {
  358. // Key 0xffff is used as a marker to indicate that the entry is not set.
  359. if (key == NORCOW_KEY_FREE) {
  360. return secfalse;
  361. }
  362. const uint8_t sector_num = norcow_sectors[norcow_write_sector];
  363. secbool ret = secfalse;
  364. const void *ptr = NULL;
  365. uint16_t len_old = 0;
  366. *found = find_item(norcow_write_sector, key, &ptr, &len_old);
  367. // Try to update the entry if it already exists.
  368. uint32_t offset = 0;
  369. if (sectrue == *found) {
  370. offset = (const uint8_t*) ptr - (const uint8_t *)norcow_ptr(norcow_write_sector, 0, NORCOW_SECTOR_SIZE);
  371. if (val != NULL && len_old == len) {
  372. ret = sectrue;
  373. ensure(flash_unlock_write(), NULL);
  374. for (uint16_t i = 0; i < len; i++) {
  375. if (sectrue != flash_write_byte(sector_num, offset + i, ((const uint8_t*)val)[i])) {
  376. ret = secfalse;
  377. break;
  378. }
  379. }
  380. ensure(flash_lock_write(), NULL);
  381. }
  382. }
  383. // If the update was not possible then write the entry as a new item.
  384. if (secfalse == ret) {
  385. // Delete the old item.
  386. if (sectrue == *found) {
  387. ensure(flash_unlock_write(), NULL);
  388. // Update the prefix to indicate that the old item has been deleted.
  389. uint32_t prefix = (uint32_t)len_old << 16;
  390. ensure(flash_write_word(sector_num, offset - NORCOW_PREFIX_LEN, prefix), NULL);
  391. // Delete the old item data.
  392. uint32_t end = offset + len_old;
  393. while (offset < end) {
  394. ensure(flash_write_word(sector_num, offset, 0x00000000), NULL);
  395. offset += NORCOW_WORD_SIZE;
  396. }
  397. ensure(flash_lock_write(), NULL);
  398. }
  399. // Check whether there is enough free space and compact if full.
  400. if (norcow_free_offset + NORCOW_PREFIX_LEN + len > NORCOW_SECTOR_SIZE) {
  401. compact();
  402. }
  403. // Write new item.
  404. uint32_t pos;
  405. ret = write_item(norcow_write_sector, norcow_free_offset, key, val, len, &pos);
  406. if (sectrue == ret) {
  407. norcow_free_offset = pos;
  408. }
  409. }
  410. return ret;
  411. }
  412. /*
  413. * Deletes the given key, returns status of the operation.
  414. */
  415. secbool norcow_delete(uint16_t key)
  416. {
  417. // Key 0xffff is used as a marker to indicate that the entry is not set.
  418. if (key == NORCOW_KEY_FREE) {
  419. return secfalse;
  420. }
  421. const uint8_t sector_num = norcow_sectors[norcow_write_sector];
  422. const void *ptr = NULL;
  423. uint16_t len = 0;
  424. if (sectrue != find_item(norcow_write_sector, key, &ptr, &len)) {
  425. return secfalse;
  426. }
  427. uint32_t offset = (const uint8_t*) ptr - (const uint8_t *)norcow_ptr(norcow_write_sector, 0, NORCOW_SECTOR_SIZE);
  428. ensure(flash_unlock_write(), NULL);
  429. // Update the prefix to indicate that the item has been deleted.
  430. uint32_t prefix = (uint32_t)len << 16;
  431. ensure(flash_write_word(sector_num, offset - NORCOW_PREFIX_LEN, prefix), NULL);
  432. // Delete the item data.
  433. uint32_t end = offset + len;
  434. while (offset < end) {
  435. ensure(flash_write_word(sector_num, offset, 0x00000000), NULL);
  436. offset += NORCOW_WORD_SIZE;
  437. }
  438. ensure(flash_lock_write(), NULL);
  439. return sectrue;
  440. }
  441. /*
  442. * Update a word in flash at the given pointer. The pointer must point
  443. * into the NORCOW area.
  444. */
  445. secbool norcow_update_word(uint16_t key, uint16_t offset, uint32_t value)
  446. {
  447. const void *ptr;
  448. uint16_t len;
  449. if (sectrue != find_item(norcow_write_sector, key, &ptr, &len)) {
  450. return secfalse;
  451. }
  452. if ((offset & 3) != 0 || offset >= len) {
  453. return secfalse;
  454. }
  455. uint32_t sector_offset = (const uint8_t*) ptr - (const uint8_t *)norcow_ptr(norcow_write_sector, 0, NORCOW_SECTOR_SIZE) + offset;
  456. ensure(flash_unlock_write(), NULL);
  457. ensure(flash_write_word(norcow_sectors[norcow_write_sector], sector_offset, value), NULL);
  458. ensure(flash_lock_write(), NULL);
  459. return sectrue;
  460. }
  461. /*
  462. * Update the value of the given key starting at the given offset.
  463. */
  464. secbool norcow_update_bytes(const uint16_t key, const uint16_t offset, const uint8_t *data, const uint16_t len)
  465. {
  466. const void *ptr;
  467. uint16_t allocated_len;
  468. if (sectrue != find_item(norcow_write_sector, key, &ptr, &allocated_len)) {
  469. return secfalse;
  470. }
  471. if (offset + len > allocated_len) {
  472. return secfalse;
  473. }
  474. uint32_t sector_offset = (const uint8_t*) ptr - (const uint8_t *)norcow_ptr(norcow_write_sector, 0, NORCOW_SECTOR_SIZE) + offset;
  475. uint8_t sector = norcow_sectors[norcow_write_sector];
  476. ensure(flash_unlock_write(), NULL);
  477. for (uint16_t i = 0; i < len; i++, sector_offset++) {
  478. ensure(flash_write_byte(sector, sector_offset, data[i]), NULL);
  479. }
  480. ensure(flash_lock_write(), NULL);
  481. return sectrue;
  482. }
  483. /*
  484. * Complete storage version upgrade
  485. */
  486. secbool norcow_upgrade_finish(void)
  487. {
  488. erase_sector(norcow_active_sector, secfalse);
  489. norcow_active_sector = norcow_write_sector;
  490. norcow_active_version = NORCOW_VERSION;
  491. return sectrue;
  492. }