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