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