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, "vs-15010", "map corrupted: %lx",
  22                                (long unsigned int)le32_to_cpu(map[0]));
  23
  24         // FIXME: add something else here
  25 }
  26
  27 #else
  28 static void check_objectid_map(struct super_block *s, __le32 * map)
  29 {;
  30 }
  31 #endif
  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 /* get unique object identifier */
  48 __u32 reiserfs_get_unused_objectid(struct reiserfs_transaction_handle *th)
  49 {
  50         struct super_block *s = th->t_super;
  51         struct reiserfs_super_block *rs = SB_DISK_SUPER_BLOCK(s);
  52         __le32 *map = objectid_map(s, rs);
  53         __u32 unused_objectid;
  54
  55         BUG_ON(!th->t_trans_id);
  56
  57         check_objectid_map(s, map);
  58
  59         reiserfs_prepare_for_journal(s, SB_BUFFER_WITH_SB(s), 1);
  60         /* comment needed -Hans */
  61         unused_objectid = le32_to_cpu(map[1]);
  62         if (unused_objectid == U32_MAX) {
  63                 reiserfs_warning(s, "reiserfs-15100", "no more object ids");
  64                 reiserfs_restore_prepared_buffer(s, SB_BUFFER_WITH_SB(s));
  65                 return 0;
  66         }
  67
  68         /* This incrementation allocates the first unused objectid. That
  69            is to say, the first entry on the objectid map is the first
  70            unused objectid, and by incrementing it we use it.  See below
  71            where we check to see if we eliminated a sequence of unused
  72            objectids.... */
  73         map[1] = cpu_to_le32(unused_objectid + 1);
  74
  75         /* Now we check to see if we eliminated the last remaining member of
  76            the first even sequence (and can eliminate the sequence by
  77            eliminating its last objectid from oids), and can collapse the
  78            first two odd sequences into one sequence.  If so, then the net
  79            result is to eliminate a pair of objectids from oids.  We do this
  80            by shifting the entire map to the left. */
  81         if (sb_oid_cursize(rs) > 2 && map[1] == map[2]) {
  82                 memmove(map + 1, map + 3,
  83                         (sb_oid_cursize(rs) - 3) * sizeof(__u32));
  84                 set_sb_oid_cursize(rs, sb_oid_cursize(rs) - 2);
  85         }
  86
  87         journal_mark_dirty(th, s, SB_BUFFER_WITH_SB(s));
  88         return unused_objectid;
  89 }
  90
  91 /* makes object identifier unused */
  92 void reiserfs_release_objectid(struct reiserfs_transaction_handle *th,
  93                                __u32 objectid_to_release)
  94 {
  95         struct super_block *s = th->t_super;
  96         struct reiserfs_super_block *rs = SB_DISK_SUPER_BLOCK(s);
  97         __le32 *map = objectid_map(s, rs);
  98         int i = 0;
  99
 100         BUG_ON(!th->t_trans_id);
 101         //return;
 102         check_objectid_map(s, map);
 103
 104         reiserfs_prepare_for_journal(s, SB_BUFFER_WITH_SB(s), 1);
 105         journal_mark_dirty(th, s, SB_BUFFER_WITH_SB(s));
 106
 107         /* start at the beginning of the objectid map (i = 0) and go to
 108            the end of it (i = disk_sb->s_oid_cursize).  Linear search is
 109            what we use, though it is possible that binary search would be
 110            more efficient after performing lots of deletions (which is
 111            when oids is large.)  We only check even i's. */
 112         while (i < sb_oid_cursize(rs)) {
 113                 if (objectid_to_release == le32_to_cpu(map[i])) {
 114                         /* This incrementation unallocates the objectid. */
 115                         //map[i]++;
 116                         le32_add_cpu(&map[i], 1);
 117
 118                         /* Did we unallocate the last member of an odd sequence, and can shrink oids? */
 119                         if (map[i] == map[i + 1]) {
 120                                 /* shrink objectid map */
 121                                 memmove(map + i, map + i + 2,
 122                                         (sb_oid_cursize(rs) - i -
 123                                          2) * sizeof(__u32));
 124                                 //disk_sb->s_oid_cursize -= 2;
 125                                 set_sb_oid_cursize(rs, sb_oid_cursize(rs) - 2);
 126
 127                                 RFALSE(sb_oid_cursize(rs) < 2 ||
 128                                        sb_oid_cursize(rs) > sb_oid_maxsize(rs),
 129                                        "vs-15005: objectid map corrupted cur_size == %d (max == %d)",
 130                                        sb_oid_cursize(rs), sb_oid_maxsize(rs));
 131                         }
 132                         return;
 133                 }
 134
 135                 if (objectid_to_release > le32_to_cpu(map[i]) &&
 136                     objectid_to_release < le32_to_cpu(map[i + 1])) {
 137                         /* size of objectid map is not changed */
 138                         if (objectid_to_release + 1 == le32_to_cpu(map[i + 1])) {
 139                                 //objectid_map[i+1]--;
 140                                 le32_add_cpu(&map[i + 1], -1);
 141                                 return;
 142                         }
 143
 144                         /* JDM comparing two little-endian values for equality -- safe */
 145                         if (sb_oid_cursize(rs) == sb_oid_maxsize(rs)) {
 146                                 /* objectid map must be expanded, but there is no space */
 147                                 PROC_INFO_INC(s, leaked_oid);
 148                                 return;
 149                         }
 150
 151                         /* expand the objectid map */
 152                         memmove(map + i + 3, map + i + 1,
 153                                 (sb_oid_cursize(rs) - i - 1) * sizeof(__u32));
 154                         map[i + 1] = cpu_to_le32(objectid_to_release);
 155                         map[i + 2] = cpu_to_le32(objectid_to_release + 1);
 156                         set_sb_oid_cursize(rs, sb_oid_cursize(rs) + 2);
 157                         return;
 158                 }
 159                 i += 2;
 160         }
 161
 162         reiserfs_error(s, "vs-15011", "tried to free free object id (%lu)",
 163                        (long unsigned)objectid_to_release);
 164 }
 165
 166 int reiserfs_convert_objectid_map_v1(struct super_block *s)
 167 {
 168         struct reiserfs_super_block *disk_sb = SB_DISK_SUPER_BLOCK(s);
 169         int cur_size = sb_oid_cursize(disk_sb);
 170         int new_size = (s->s_blocksize - SB_SIZE) / sizeof(__u32) / 2 * 2;
 171         int old_max = sb_oid_maxsize(disk_sb);
 172         struct reiserfs_super_block_v1 *disk_sb_v1;
 173         __le32 *objectid_map, *new_objectid_map;
 174         int i;
 175
 176         disk_sb_v1 =
 177             (struct reiserfs_super_block_v1 *)(SB_BUFFER_WITH_SB(s)->b_data);
 178         objectid_map = (__le32 *) (disk_sb_v1 + 1);
 179         new_objectid_map = (__le32 *) (disk_sb + 1);
 180
 181         if (cur_size > new_size) {
 182                 /* mark everyone used that was listed as free at the end of the objectid
 183                  ** map
 184                  */
 185                 objectid_map[new_size - 1] = objectid_map[cur_size - 1];
 186                 set_sb_oid_cursize(disk_sb, new_size);
 187         }
 188         /* move the smaller objectid map past the end of the new super */
 189         for (i = new_size - 1; i >= 0; i--) {
 190                 objectid_map[i + (old_max - new_size)] = objectid_map[i];
 191         }
 192
 193         /* set the max size so we don't overflow later */
 194         set_sb_oid_maxsize(disk_sb, new_size);
 195
 196         /* Zero out label and generate random UUID */
 197         memset(disk_sb->s_label, 0, sizeof(disk_sb->s_label));
 198         generate_random_uuid(disk_sb->s_uuid);
 199
 200         /* finally, zero out the unused chunk of the new super */
 201         memset(disk_sb->s_unused, 0, sizeof(disk_sb->s_unused));
 202         return 0;
 203 }