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