key.h 14 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536
  1. /* SPDX-License-Identifier: GPL-2.0+ */
  2. /*
  3. * This file is part of UBIFS.
  4. *
  5. * Copyright (C) 2006-2008 Nokia Corporation.
  6. *
  7. * Authors: Artem Bityutskiy (Битюцкий Артём)
  8. * Adrian Hunter
  9. */
  10. /*
  11. * This header contains various key-related definitions and helper function.
  12. * UBIFS allows several key schemes, so we access key fields only via these
  13. * helpers. At the moment only one key scheme is supported.
  14. *
  15. * Simple key scheme
  16. * ~~~~~~~~~~~~~~~~~
  17. *
  18. * Keys are 64-bits long. First 32-bits are inode number (parent inode number
  19. * in case of direntry key). Next 3 bits are node type. The last 29 bits are
  20. * 4KiB offset in case of inode node, and direntry hash in case of a direntry
  21. * node. We use "r5" hash borrowed from reiserfs.
  22. */
  23. #ifndef __UBIFS_KEY_H__
  24. #define __UBIFS_KEY_H__
  25. /**
  26. * key_mask_hash - mask a valid hash value.
  27. * @val: value to be masked
  28. *
  29. * We use hash values as offset in directories, so values %0 and %1 are
  30. * reserved for "." and "..". %2 is reserved for "end of readdir" marker. This
  31. * function makes sure the reserved values are not used.
  32. */
  33. static inline uint32_t key_mask_hash(uint32_t hash)
  34. {
  35. hash &= UBIFS_S_KEY_HASH_MASK;
  36. if (unlikely(hash <= 2))
  37. hash += 3;
  38. return hash;
  39. }
  40. /**
  41. * key_r5_hash - R5 hash function (borrowed from reiserfs).
  42. * @s: direntry name
  43. * @len: name length
  44. */
  45. static inline uint32_t key_r5_hash(const char *s, int len)
  46. {
  47. uint32_t a = 0;
  48. const signed char *str = (const signed char *)s;
  49. while (*str) {
  50. a += *str << 4;
  51. a += *str >> 4;
  52. a *= 11;
  53. str++;
  54. }
  55. return key_mask_hash(a);
  56. }
  57. /**
  58. * key_test_hash - testing hash function.
  59. * @str: direntry name
  60. * @len: name length
  61. */
  62. static inline uint32_t key_test_hash(const char *str, int len)
  63. {
  64. uint32_t a = 0;
  65. len = min_t(uint32_t, len, 4);
  66. memcpy(&a, str, len);
  67. return key_mask_hash(a);
  68. }
  69. /**
  70. * ino_key_init - initialize inode key.
  71. * @c: UBIFS file-system description object
  72. * @key: key to initialize
  73. * @inum: inode number
  74. */
  75. static inline void ino_key_init(const struct ubifs_info *c,
  76. union ubifs_key *key, ino_t inum)
  77. {
  78. key->u32[0] = inum;
  79. key->u32[1] = UBIFS_INO_KEY << UBIFS_S_KEY_BLOCK_BITS;
  80. }
  81. /**
  82. * ino_key_init_flash - initialize on-flash inode key.
  83. * @c: UBIFS file-system description object
  84. * @k: key to initialize
  85. * @inum: inode number
  86. */
  87. static inline void ino_key_init_flash(const struct ubifs_info *c, void *k,
  88. ino_t inum)
  89. {
  90. union ubifs_key *key = k;
  91. key->j32[0] = cpu_to_le32(inum);
  92. key->j32[1] = cpu_to_le32(UBIFS_INO_KEY << UBIFS_S_KEY_BLOCK_BITS);
  93. memset(k + 8, 0, UBIFS_MAX_KEY_LEN - 8);
  94. }
  95. /**
  96. * lowest_ino_key - get the lowest possible inode key.
  97. * @c: UBIFS file-system description object
  98. * @key: key to initialize
  99. * @inum: inode number
  100. */
  101. static inline void lowest_ino_key(const struct ubifs_info *c,
  102. union ubifs_key *key, ino_t inum)
  103. {
  104. key->u32[0] = inum;
  105. key->u32[1] = 0;
  106. }
  107. /**
  108. * highest_ino_key - get the highest possible inode key.
  109. * @c: UBIFS file-system description object
  110. * @key: key to initialize
  111. * @inum: inode number
  112. */
  113. static inline void highest_ino_key(const struct ubifs_info *c,
  114. union ubifs_key *key, ino_t inum)
  115. {
  116. key->u32[0] = inum;
  117. key->u32[1] = 0xffffffff;
  118. }
  119. /**
  120. * dent_key_init - initialize directory entry key.
  121. * @c: UBIFS file-system description object
  122. * @key: key to initialize
  123. * @inum: parent inode number
  124. * @nm: direntry name and length
  125. */
  126. static inline void dent_key_init(const struct ubifs_info *c,
  127. union ubifs_key *key, ino_t inum,
  128. const struct qstr *nm)
  129. {
  130. uint32_t hash = c->key_hash(nm->name, nm->len);
  131. ubifs_assert(!(hash & ~UBIFS_S_KEY_HASH_MASK));
  132. key->u32[0] = inum;
  133. key->u32[1] = hash | (UBIFS_DENT_KEY << UBIFS_S_KEY_HASH_BITS);
  134. }
  135. /**
  136. * dent_key_init_hash - initialize directory entry key without re-calculating
  137. * hash function.
  138. * @c: UBIFS file-system description object
  139. * @key: key to initialize
  140. * @inum: parent inode number
  141. * @hash: direntry name hash
  142. */
  143. static inline void dent_key_init_hash(const struct ubifs_info *c,
  144. union ubifs_key *key, ino_t inum,
  145. uint32_t hash)
  146. {
  147. ubifs_assert(!(hash & ~UBIFS_S_KEY_HASH_MASK));
  148. key->u32[0] = inum;
  149. key->u32[1] = hash | (UBIFS_DENT_KEY << UBIFS_S_KEY_HASH_BITS);
  150. }
  151. /**
  152. * dent_key_init_flash - initialize on-flash directory entry key.
  153. * @c: UBIFS file-system description object
  154. * @k: key to initialize
  155. * @inum: parent inode number
  156. * @nm: direntry name and length
  157. */
  158. static inline void dent_key_init_flash(const struct ubifs_info *c, void *k,
  159. ino_t inum, const struct qstr *nm)
  160. {
  161. union ubifs_key *key = k;
  162. uint32_t hash = c->key_hash(nm->name, nm->len);
  163. ubifs_assert(!(hash & ~UBIFS_S_KEY_HASH_MASK));
  164. key->j32[0] = cpu_to_le32(inum);
  165. key->j32[1] = cpu_to_le32(hash |
  166. (UBIFS_DENT_KEY << UBIFS_S_KEY_HASH_BITS));
  167. memset(k + 8, 0, UBIFS_MAX_KEY_LEN - 8);
  168. }
  169. /**
  170. * lowest_dent_key - get the lowest possible directory entry key.
  171. * @c: UBIFS file-system description object
  172. * @key: where to store the lowest key
  173. * @inum: parent inode number
  174. */
  175. static inline void lowest_dent_key(const struct ubifs_info *c,
  176. union ubifs_key *key, ino_t inum)
  177. {
  178. key->u32[0] = inum;
  179. key->u32[1] = UBIFS_DENT_KEY << UBIFS_S_KEY_HASH_BITS;
  180. }
  181. /**
  182. * xent_key_init - initialize extended attribute entry key.
  183. * @c: UBIFS file-system description object
  184. * @key: key to initialize
  185. * @inum: host inode number
  186. * @nm: extended attribute entry name and length
  187. */
  188. static inline void xent_key_init(const struct ubifs_info *c,
  189. union ubifs_key *key, ino_t inum,
  190. const struct qstr *nm)
  191. {
  192. uint32_t hash = c->key_hash(nm->name, nm->len);
  193. ubifs_assert(!(hash & ~UBIFS_S_KEY_HASH_MASK));
  194. key->u32[0] = inum;
  195. key->u32[1] = hash | (UBIFS_XENT_KEY << UBIFS_S_KEY_HASH_BITS);
  196. }
  197. /**
  198. * xent_key_init_flash - initialize on-flash extended attribute entry key.
  199. * @c: UBIFS file-system description object
  200. * @k: key to initialize
  201. * @inum: host inode number
  202. * @nm: extended attribute entry name and length
  203. */
  204. static inline void xent_key_init_flash(const struct ubifs_info *c, void *k,
  205. ino_t inum, const struct qstr *nm)
  206. {
  207. union ubifs_key *key = k;
  208. uint32_t hash = c->key_hash(nm->name, nm->len);
  209. ubifs_assert(!(hash & ~UBIFS_S_KEY_HASH_MASK));
  210. key->j32[0] = cpu_to_le32(inum);
  211. key->j32[1] = cpu_to_le32(hash |
  212. (UBIFS_XENT_KEY << UBIFS_S_KEY_HASH_BITS));
  213. memset(k + 8, 0, UBIFS_MAX_KEY_LEN - 8);
  214. }
  215. /**
  216. * lowest_xent_key - get the lowest possible extended attribute entry key.
  217. * @c: UBIFS file-system description object
  218. * @key: where to store the lowest key
  219. * @inum: host inode number
  220. */
  221. static inline void lowest_xent_key(const struct ubifs_info *c,
  222. union ubifs_key *key, ino_t inum)
  223. {
  224. key->u32[0] = inum;
  225. key->u32[1] = UBIFS_XENT_KEY << UBIFS_S_KEY_HASH_BITS;
  226. }
  227. /**
  228. * data_key_init - initialize data key.
  229. * @c: UBIFS file-system description object
  230. * @key: key to initialize
  231. * @inum: inode number
  232. * @block: block number
  233. */
  234. static inline void data_key_init(const struct ubifs_info *c,
  235. union ubifs_key *key, ino_t inum,
  236. unsigned int block)
  237. {
  238. ubifs_assert(!(block & ~UBIFS_S_KEY_BLOCK_MASK));
  239. key->u32[0] = inum;
  240. key->u32[1] = block | (UBIFS_DATA_KEY << UBIFS_S_KEY_BLOCK_BITS);
  241. }
  242. /**
  243. * highest_data_key - get the highest possible data key for an inode.
  244. * @c: UBIFS file-system description object
  245. * @key: key to initialize
  246. * @inum: inode number
  247. */
  248. static inline void highest_data_key(const struct ubifs_info *c,
  249. union ubifs_key *key, ino_t inum)
  250. {
  251. data_key_init(c, key, inum, UBIFS_S_KEY_BLOCK_MASK);
  252. }
  253. /**
  254. * trun_key_init - initialize truncation node key.
  255. * @c: UBIFS file-system description object
  256. * @key: key to initialize
  257. * @inum: inode number
  258. *
  259. * Note, UBIFS does not have truncation keys on the media and this function is
  260. * only used for purposes of replay.
  261. */
  262. static inline void trun_key_init(const struct ubifs_info *c,
  263. union ubifs_key *key, ino_t inum)
  264. {
  265. key->u32[0] = inum;
  266. key->u32[1] = UBIFS_TRUN_KEY << UBIFS_S_KEY_BLOCK_BITS;
  267. }
  268. /**
  269. * invalid_key_init - initialize invalid node key.
  270. * @c: UBIFS file-system description object
  271. * @key: key to initialize
  272. *
  273. * This is a helper function which marks a @key object as invalid.
  274. */
  275. static inline void invalid_key_init(const struct ubifs_info *c,
  276. union ubifs_key *key)
  277. {
  278. key->u32[0] = 0xDEADBEAF;
  279. key->u32[1] = UBIFS_INVALID_KEY;
  280. }
  281. /**
  282. * key_type - get key type.
  283. * @c: UBIFS file-system description object
  284. * @key: key to get type of
  285. */
  286. static inline int key_type(const struct ubifs_info *c,
  287. const union ubifs_key *key)
  288. {
  289. return key->u32[1] >> UBIFS_S_KEY_BLOCK_BITS;
  290. }
  291. /**
  292. * key_type_flash - get type of a on-flash formatted key.
  293. * @c: UBIFS file-system description object
  294. * @k: key to get type of
  295. */
  296. static inline int key_type_flash(const struct ubifs_info *c, const void *k)
  297. {
  298. const union ubifs_key *key = k;
  299. return le32_to_cpu(key->j32[1]) >> UBIFS_S_KEY_BLOCK_BITS;
  300. }
  301. /**
  302. * key_inum - fetch inode number from key.
  303. * @c: UBIFS file-system description object
  304. * @k: key to fetch inode number from
  305. */
  306. static inline ino_t key_inum(const struct ubifs_info *c, const void *k)
  307. {
  308. const union ubifs_key *key = k;
  309. return key->u32[0];
  310. }
  311. /**
  312. * key_inum_flash - fetch inode number from an on-flash formatted key.
  313. * @c: UBIFS file-system description object
  314. * @k: key to fetch inode number from
  315. */
  316. static inline ino_t key_inum_flash(const struct ubifs_info *c, const void *k)
  317. {
  318. const union ubifs_key *key = k;
  319. return le32_to_cpu(key->j32[0]);
  320. }
  321. /**
  322. * key_hash - get directory entry hash.
  323. * @c: UBIFS file-system description object
  324. * @key: the key to get hash from
  325. */
  326. static inline uint32_t key_hash(const struct ubifs_info *c,
  327. const union ubifs_key *key)
  328. {
  329. return key->u32[1] & UBIFS_S_KEY_HASH_MASK;
  330. }
  331. /**
  332. * key_hash_flash - get directory entry hash from an on-flash formatted key.
  333. * @c: UBIFS file-system description object
  334. * @k: the key to get hash from
  335. */
  336. static inline uint32_t key_hash_flash(const struct ubifs_info *c, const void *k)
  337. {
  338. const union ubifs_key *key = k;
  339. return le32_to_cpu(key->j32[1]) & UBIFS_S_KEY_HASH_MASK;
  340. }
  341. /**
  342. * key_block - get data block number.
  343. * @c: UBIFS file-system description object
  344. * @key: the key to get the block number from
  345. */
  346. static inline unsigned int key_block(const struct ubifs_info *c,
  347. const union ubifs_key *key)
  348. {
  349. return key->u32[1] & UBIFS_S_KEY_BLOCK_MASK;
  350. }
  351. /**
  352. * key_block_flash - get data block number from an on-flash formatted key.
  353. * @c: UBIFS file-system description object
  354. * @k: the key to get the block number from
  355. */
  356. static inline unsigned int key_block_flash(const struct ubifs_info *c,
  357. const void *k)
  358. {
  359. const union ubifs_key *key = k;
  360. return le32_to_cpu(key->j32[1]) & UBIFS_S_KEY_BLOCK_MASK;
  361. }
  362. /**
  363. * key_read - transform a key to in-memory format.
  364. * @c: UBIFS file-system description object
  365. * @from: the key to transform
  366. * @to: the key to store the result
  367. */
  368. static inline void key_read(const struct ubifs_info *c, const void *from,
  369. union ubifs_key *to)
  370. {
  371. const union ubifs_key *f = from;
  372. to->u32[0] = le32_to_cpu(f->j32[0]);
  373. to->u32[1] = le32_to_cpu(f->j32[1]);
  374. }
  375. /**
  376. * key_write - transform a key from in-memory format.
  377. * @c: UBIFS file-system description object
  378. * @from: the key to transform
  379. * @to: the key to store the result
  380. */
  381. static inline void key_write(const struct ubifs_info *c,
  382. const union ubifs_key *from, void *to)
  383. {
  384. union ubifs_key *t = to;
  385. t->j32[0] = cpu_to_le32(from->u32[0]);
  386. t->j32[1] = cpu_to_le32(from->u32[1]);
  387. memset(to + 8, 0, UBIFS_MAX_KEY_LEN - 8);
  388. }
  389. /**
  390. * key_write_idx - transform a key from in-memory format for the index.
  391. * @c: UBIFS file-system description object
  392. * @from: the key to transform
  393. * @to: the key to store the result
  394. */
  395. static inline void key_write_idx(const struct ubifs_info *c,
  396. const union ubifs_key *from, void *to)
  397. {
  398. union ubifs_key *t = to;
  399. t->j32[0] = cpu_to_le32(from->u32[0]);
  400. t->j32[1] = cpu_to_le32(from->u32[1]);
  401. }
  402. /**
  403. * key_copy - copy a key.
  404. * @c: UBIFS file-system description object
  405. * @from: the key to copy from
  406. * @to: the key to copy to
  407. */
  408. static inline void key_copy(const struct ubifs_info *c,
  409. const union ubifs_key *from, union ubifs_key *to)
  410. {
  411. to->u64[0] = from->u64[0];
  412. }
  413. /**
  414. * keys_cmp - compare keys.
  415. * @c: UBIFS file-system description object
  416. * @key1: the first key to compare
  417. * @key2: the second key to compare
  418. *
  419. * This function compares 2 keys and returns %-1 if @key1 is less than
  420. * @key2, %0 if the keys are equivalent and %1 if @key1 is greater than @key2.
  421. */
  422. static inline int keys_cmp(const struct ubifs_info *c,
  423. const union ubifs_key *key1,
  424. const union ubifs_key *key2)
  425. {
  426. if (key1->u32[0] < key2->u32[0])
  427. return -1;
  428. if (key1->u32[0] > key2->u32[0])
  429. return 1;
  430. if (key1->u32[1] < key2->u32[1])
  431. return -1;
  432. if (key1->u32[1] > key2->u32[1])
  433. return 1;
  434. return 0;
  435. }
  436. /**
  437. * keys_eq - determine if keys are equivalent.
  438. * @c: UBIFS file-system description object
  439. * @key1: the first key to compare
  440. * @key2: the second key to compare
  441. *
  442. * This function compares 2 keys and returns %1 if @key1 is equal to @key2 and
  443. * %0 if not.
  444. */
  445. static inline int keys_eq(const struct ubifs_info *c,
  446. const union ubifs_key *key1,
  447. const union ubifs_key *key2)
  448. {
  449. if (key1->u32[0] != key2->u32[0])
  450. return 0;
  451. if (key1->u32[1] != key2->u32[1])
  452. return 0;
  453. return 1;
  454. }
  455. /**
  456. * is_hash_key - is a key vulnerable to hash collisions.
  457. * @c: UBIFS file-system description object
  458. * @key: key
  459. *
  460. * This function returns %1 if @key is a hashed key or %0 otherwise.
  461. */
  462. static inline int is_hash_key(const struct ubifs_info *c,
  463. const union ubifs_key *key)
  464. {
  465. int type = key_type(c, key);
  466. return type == UBIFS_DENT_KEY || type == UBIFS_XENT_KEY;
  467. }
  468. /**
  469. * key_max_inode_size - get maximum file size allowed by current key format.
  470. * @c: UBIFS file-system description object
  471. */
  472. static inline unsigned long long key_max_inode_size(const struct ubifs_info *c)
  473. {
  474. switch (c->key_fmt) {
  475. case UBIFS_SIMPLE_KEY_FMT:
  476. return (1ULL << UBIFS_S_KEY_BLOCK_BITS) * UBIFS_BLOCK_SIZE;
  477. default:
  478. return 0;
  479. }
  480. }
  481. #endif /* !__UBIFS_KEY_H__ */