fs/reiserfs/objectid.c

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