The Design and Implementation of the FreeBSD Operating System, Second Edition
Now available: The Design and Implementation of the FreeBSD Operating System (Second Edition)


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]

FreeBSD/Linux Kernel Cross Reference
sys/fs/reiserfs/objectid.c

Version: -  FREEBSD  -  FREEBSD-13-STABLE  -  FREEBSD-13-0  -  FREEBSD-12-STABLE  -  FREEBSD-12-0  -  FREEBSD-11-STABLE  -  FREEBSD-11-0  -  FREEBSD-10-STABLE  -  FREEBSD-10-0  -  FREEBSD-9-STABLE  -  FREEBSD-9-0  -  FREEBSD-8-STABLE  -  FREEBSD-8-0  -  FREEBSD-7-STABLE  -  FREEBSD-7-0  -  FREEBSD-6-STABLE  -  FREEBSD-6-0  -  FREEBSD-5-STABLE  -  FREEBSD-5-0  -  FREEBSD-4-STABLE  -  FREEBSD-3-STABLE  -  FREEBSD22  -  l41  -  OPENBSD  -  linux-2.6  -  MK84  -  PLAN9  -  xnu-8792 
SearchContext: -  none  -  3  -  10 

    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 

Cache object: 7d04f4c19a7fffdf030be169058070f9


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]


This page is part of the FreeBSD/Linux Linux Kernel Cross-Reference, and was automatically generated using a modified version of the LXR engine.