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 } 208