objectid.c 6.8 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216
  1. /*
  2. * Copyright 2000 by Hans Reiser, licensing governed by reiserfs/README
  3. */
  4. #include <linux/string.h>
  5. #include <linux/time.h>
  6. #include <linux/uuid.h>
  7. #include "reiserfs.h"
  8. /* find where objectid map starts */
  9. #define objectid_map(s,rs) (old_format_only (s) ? \
  10. (__le32 *)((struct reiserfs_super_block_v1 *)(rs) + 1) :\
  11. (__le32 *)((rs) + 1))
  12. #ifdef CONFIG_REISERFS_CHECK
  13. static void check_objectid_map(struct super_block *s, __le32 * map)
  14. {
  15. if (le32_to_cpu(map[0]) != 1)
  16. reiserfs_panic(s, "vs-15010", "map corrupted: %lx",
  17. (long unsigned int)le32_to_cpu(map[0]));
  18. /* FIXME: add something else here */
  19. }
  20. #else
  21. static void check_objectid_map(struct super_block *s, __le32 * map)
  22. {;
  23. }
  24. #endif
  25. /*
  26. * When we allocate objectids we allocate the first unused objectid.
  27. * Each sequence of objectids in use (the odd sequences) is followed
  28. * by a sequence of objectids not in use (the even sequences). We
  29. * only need to record the last objectid in each of these sequences
  30. * (both the odd and even sequences) in order to fully define the
  31. * boundaries of the sequences. A consequence of allocating the first
  32. * objectid not in use is that under most conditions this scheme is
  33. * extremely compact. The exception is immediately after a sequence
  34. * of operations which deletes a large number of objects of
  35. * non-sequential objectids, and even then it will become compact
  36. * again as soon as more objects are created. Note that many
  37. * interesting optimizations of layout could result from complicating
  38. * objectid assignment, but we have deferred making them for now.
  39. */
  40. /* get unique object identifier */
  41. __u32 reiserfs_get_unused_objectid(struct reiserfs_transaction_handle *th)
  42. {
  43. struct super_block *s = th->t_super;
  44. struct reiserfs_super_block *rs = SB_DISK_SUPER_BLOCK(s);
  45. __le32 *map = objectid_map(s, rs);
  46. __u32 unused_objectid;
  47. BUG_ON(!th->t_trans_id);
  48. check_objectid_map(s, map);
  49. reiserfs_prepare_for_journal(s, SB_BUFFER_WITH_SB(s), 1);
  50. /* comment needed -Hans */
  51. unused_objectid = le32_to_cpu(map[1]);
  52. if (unused_objectid == U32_MAX) {
  53. reiserfs_warning(s, "reiserfs-15100", "no more object ids");
  54. reiserfs_restore_prepared_buffer(s, SB_BUFFER_WITH_SB(s));
  55. return 0;
  56. }
  57. /*
  58. * This incrementation allocates the first unused objectid. That
  59. * is to say, the first entry on the objectid map is the first
  60. * unused objectid, and by incrementing it we use it. See below
  61. * where we check to see if we eliminated a sequence of unused
  62. * objectids....
  63. */
  64. map[1] = cpu_to_le32(unused_objectid + 1);
  65. /*
  66. * Now we check to see if we eliminated the last remaining member of
  67. * the first even sequence (and can eliminate the sequence by
  68. * eliminating its last objectid from oids), and can collapse the
  69. * first two odd sequences into one sequence. If so, then the net
  70. * result is to eliminate a pair of objectids from oids. We do this
  71. * by shifting the entire map to the left.
  72. */
  73. if (sb_oid_cursize(rs) > 2 && map[1] == map[2]) {
  74. memmove(map + 1, map + 3,
  75. (sb_oid_cursize(rs) - 3) * sizeof(__u32));
  76. set_sb_oid_cursize(rs, sb_oid_cursize(rs) - 2);
  77. }
  78. journal_mark_dirty(th, SB_BUFFER_WITH_SB(s));
  79. return unused_objectid;
  80. }
  81. /* makes object identifier unused */
  82. void reiserfs_release_objectid(struct reiserfs_transaction_handle *th,
  83. __u32 objectid_to_release)
  84. {
  85. struct super_block *s = th->t_super;
  86. struct reiserfs_super_block *rs = SB_DISK_SUPER_BLOCK(s);
  87. __le32 *map = objectid_map(s, rs);
  88. int i = 0;
  89. BUG_ON(!th->t_trans_id);
  90. /*return; */
  91. check_objectid_map(s, map);
  92. reiserfs_prepare_for_journal(s, SB_BUFFER_WITH_SB(s), 1);
  93. journal_mark_dirty(th, SB_BUFFER_WITH_SB(s));
  94. /*
  95. * start at the beginning of the objectid map (i = 0) and go to
  96. * the end of it (i = disk_sb->s_oid_cursize). Linear search is
  97. * what we use, though it is possible that binary search would be
  98. * more efficient after performing lots of deletions (which is
  99. * when oids is large.) We only check even i's.
  100. */
  101. while (i < sb_oid_cursize(rs)) {
  102. if (objectid_to_release == le32_to_cpu(map[i])) {
  103. /* This incrementation unallocates the objectid. */
  104. le32_add_cpu(&map[i], 1);
  105. /*
  106. * Did we unallocate the last member of an
  107. * odd sequence, and can shrink oids?
  108. */
  109. if (map[i] == map[i + 1]) {
  110. /* shrink objectid map */
  111. memmove(map + i, map + i + 2,
  112. (sb_oid_cursize(rs) - i -
  113. 2) * sizeof(__u32));
  114. set_sb_oid_cursize(rs, sb_oid_cursize(rs) - 2);
  115. RFALSE(sb_oid_cursize(rs) < 2 ||
  116. sb_oid_cursize(rs) > sb_oid_maxsize(rs),
  117. "vs-15005: objectid map corrupted cur_size == %d (max == %d)",
  118. sb_oid_cursize(rs), sb_oid_maxsize(rs));
  119. }
  120. return;
  121. }
  122. if (objectid_to_release > le32_to_cpu(map[i]) &&
  123. objectid_to_release < le32_to_cpu(map[i + 1])) {
  124. /* size of objectid map is not changed */
  125. if (objectid_to_release + 1 == le32_to_cpu(map[i + 1])) {
  126. le32_add_cpu(&map[i + 1], -1);
  127. return;
  128. }
  129. /*
  130. * JDM comparing two little-endian values for
  131. * equality -- safe
  132. */
  133. /*
  134. * objectid map must be expanded, but
  135. * there is no space
  136. */
  137. if (sb_oid_cursize(rs) == sb_oid_maxsize(rs)) {
  138. PROC_INFO_INC(s, leaked_oid);
  139. return;
  140. }
  141. /* expand the objectid map */
  142. memmove(map + i + 3, map + i + 1,
  143. (sb_oid_cursize(rs) - i - 1) * sizeof(__u32));
  144. map[i + 1] = cpu_to_le32(objectid_to_release);
  145. map[i + 2] = cpu_to_le32(objectid_to_release + 1);
  146. set_sb_oid_cursize(rs, sb_oid_cursize(rs) + 2);
  147. return;
  148. }
  149. i += 2;
  150. }
  151. reiserfs_error(s, "vs-15011", "tried to free free object id (%lu)",
  152. (long unsigned)objectid_to_release);
  153. }
  154. int reiserfs_convert_objectid_map_v1(struct super_block *s)
  155. {
  156. struct reiserfs_super_block *disk_sb = SB_DISK_SUPER_BLOCK(s);
  157. int cur_size = sb_oid_cursize(disk_sb);
  158. int new_size = (s->s_blocksize - SB_SIZE) / sizeof(__u32) / 2 * 2;
  159. int old_max = sb_oid_maxsize(disk_sb);
  160. struct reiserfs_super_block_v1 *disk_sb_v1;
  161. __le32 *objectid_map;
  162. int i;
  163. disk_sb_v1 =
  164. (struct reiserfs_super_block_v1 *)(SB_BUFFER_WITH_SB(s)->b_data);
  165. objectid_map = (__le32 *) (disk_sb_v1 + 1);
  166. if (cur_size > new_size) {
  167. /*
  168. * mark everyone used that was listed as free at
  169. * the end of the objectid map
  170. */
  171. objectid_map[new_size - 1] = objectid_map[cur_size - 1];
  172. set_sb_oid_cursize(disk_sb, new_size);
  173. }
  174. /* move the smaller objectid map past the end of the new super */
  175. for (i = new_size - 1; i >= 0; i--) {
  176. objectid_map[i + (old_max - new_size)] = objectid_map[i];
  177. }
  178. /* set the max size so we don't overflow later */
  179. set_sb_oid_maxsize(disk_sb, new_size);
  180. /* Zero out label and generate random UUID */
  181. memset(disk_sb->s_label, 0, sizeof(disk_sb->s_label));
  182. generate_random_uuid(disk_sb->s_uuid);
  183. /* finally, zero out the unused chunk of the new super */
  184. memset(disk_sb->s_unused, 0, sizeof(disk_sb->s_unused));
  185. return 0;
  186. }