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