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 }