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