fs/reiserfs/objectid.c

   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 }