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