Ocfs2 allocation reservations
Subsystems (2)
cover Ocfs2 allocation reservations
The following patches comprise my latest work on enabling larger contiguous allocations in Ocfs2 in the presence of multiple threads. The patches have been through much more testing since my last round. At this point, I'd say they're ready for wider consumption and of course, more review :)
Similarly to the last series, reservations only operate on the local alloc bitmap. The code knows nothing of inodes and allocators however, so we can extend it to the global bitmap (should the need arise) at a future date.
Changes from the last series are numerous. The biggest one however, is that reservations (when enabled) are no longer 'advisory' and represent an actual region of free bits in the local alloc file. The local alloc code obeys reservations unconditionally.
The reason I made this change is because I saw a breakdown in allocation (back to worst-case) on longer running tests, or those with many threads. Those tests it turned out, were exposing "corner cases" in the code where reservations could no longer be honored due to bits having been set in the local alloc bitmap. Better window replacement (and tracking) policy became quite convoluted when the state of the local alloc bitmap wasn't quite known. It is far simpler to just consult the bitmap for windows, and my testing results showed that it worked better too.
This differs from file systems like ext4 (which I used for inspiration), but our allocation strategy differs greatly. Whereas ext4 may have many different block groups in play during a multi-threaded write we only have the single (and relatively smaller) local alloc window. Reservations can afford to be advisory for ext4, in Ocfs2 however we need them to be honored.
As for results, I provide one of my recent test runs on a 4k/4k file system:
dd if=/dev/urandom of=/ocfs2/1 bs=4096 count=10000 & dd if=/dev/urandom of=/ocfs2/2 bs=4096 count=10000 & dd if=/dev/urandom of=/ocfs2/3 bs=4096 count=10000 &
resv_level=0
Inode: 16920 % fragmented: 93.48 clusters: 10000 extents: 9348 score: 23931
Inode: 16921 % fragmented: 84.75 clusters: 10000 extents: 8475 score: 21696
Inode: 16922 % fragmented: 95.50 clusters: 10000 extents: 9550 score: 24448
resv_level=5 (defaults changed a bit, this means '128 blocks per reservation'):
Inode: 16916 % fragmented: 1.66 clusters: 10000 extents: 166 score: 425
Inode: 16917 % fragmented: 1.71 clusters: 10000 extents: 171 score: 438
Inode: 16918 % fragmented: 1.58 clusters: 10000 extents: 158 score: 404
Thanks in advance,
--Mark
PATCH 1/4 ocfs2: allocation reservations
This patch improves Ocfs2 allocation policy by allowing an inode to reserve a portion of the local alloc bitmap for itself. The reserved portion (allocation window) is advisory in that other allocation windows might steal it if the local alloc bitmap becomes full. Otherwise, the reservations are honored and guaranteed to be free. When the local alloc window is moved to a different portion of the bitmap, existing reservations are discarded.
Reservation windows are represented internally by a red-black tree. Within that tree, each node represents the reservation window of one inode. An LRU of active reservations is also maintained. When new data is written, we allocate it from the inodes window. When all bits in a window are exhausted, we allocate a new one as close to the previous one as possible. Should we not find free space, an existing reservation is pulled off the LRU and cannibalized.
--- Documentation/filesystems/ocfs2.txt | 3 + fs/ocfs2/Makefile | 1 + fs/ocfs2/cluster/masklog.c | 1 + fs/ocfs2/cluster/masklog.h | 1 + fs/ocfs2/localalloc.c | 55 ++- fs/ocfs2/ocfs2.h | 5 + fs/ocfs2/reservations.c | 939 +++++++++++++++++++++++++++++++++++ fs/ocfs2/reservations.h | 159 ++++++ fs/ocfs2/suballoc.h | 2 + fs/ocfs2/super.c | 25 + 10 files changed, 1185 insertions(+), 6 deletions(-) create mode 100644 fs/ocfs2/reservations.c create mode 100644 fs/ocfs2/reservations.h
Documentation/filesystems/ocfs2.txt +3 -0
@@ -80,3 +80,6 @@ user_xattr (*) Enables Extended User Attributes. nouser_xattr Disables Extended User Attributes. acl Enables POSIX Access Control Lists support. noacl (*) Disables POSIX Access Control Lists support. +resv_level=4 (*) Set how agressive allocation reservations will be. + Valid values are between 0 (reservations off) to 8 + (maximum space for reservations).
fs/ocfs2/Makefile +1 -0
@@ -29,6 +29,7 @@ ocfs2-objs := \ mmap.o \ namei.o \ refcounttree.o \ + reservations.o \ resize.o \ slot_map.o \ suballoc.o \
fs/ocfs2/cluster/masklog.c +1 -0
@@ -115,6 +115,7 @@ static struct mlog_attribute mlog_attrs[MLOG_MAX_BITS] = {define_mask (ERROR ),define_mask (NOTICE ),define_mask (KTHREAD ), + define_mask(RESERVATIONS), };static struct attribute *mlog_attr_ptrs[MLOG_MAX_BITS ] = {NULL , };
fs/ocfs2/cluster/masklog.h +1 -0
@@ -118,6 +118,7 @@#define ML_ERROR 0x0000000100000000ULL/* sent to KERN_ERR */ #define ML_NOTICE 0x0000000200000000ULL/* setn to KERN_NOTICE */ #define ML_KTHREAD 0x0000000400000000ULL/* kernel thread activity */ +#define ML_RESERVATIONS 0x0000000800000000ULL/* ocfs2 alloc reservations */ #define MLOG_INITIAL_AND_MASK (ML_ERROR|ML_NOTICE)#define MLOG_INITIAL_NOT_MASK (ML_ENTRY|ML_EXIT)
fs/ocfs2/localalloc.c +49 -6
115 lines not on this page · raw message
fs/ocfs2/ocfs2.h +5 -0
@@ -46,6 +46,7 @@/* For struct ocfs2_blockcheck_stats */ #include "blockcheck.h" +#include "reservations.h" /* Caching of metadata buffers */
@@ -346,6 +347,10 @@ struct ocfs2_superu64 la_last_gd; +struct ocfs2_reservation_map osb_la_resmap; + +unsigned int osb_resv_level; +/* Next three fields are for local node slot recovery during * mount. */ int dirty;
fs/ocfs2/reservations.c new file +939 -0
939 lines not on this page · raw message
fs/ocfs2/reservations.h new file +159 -0
159 lines not on this page · raw message
fs/ocfs2/suballoc.h +2 -0
@@ -54,6 +54,8 @@ struct ocfs2_alloc_context {u64 ac_last_group;u64 ac_max_block;/* Highest block number to allocate. 0 is is the same as ~0 - unlimited */ + +struct ocfs2_alloc_reservation *ac_resv; };void ocfs2_free_alloc_context (struct ocfs2_alloc_context *ac);
fs/ocfs2/super.c +25 -0
@@ -94,6 +94,7 @@ struct mount_optionsunsigned int atime_quantum;signed short slot;unsigned int localalloc_opt; +unsigned int resv_level;char cluster_stack[OCFS2_STACK_LABEL_LEN +1 ]; };
@@ -175,6 +176,7 @@ enum { Opt_noacl, Opt_usrquota, Opt_grpquota, + Opt_resv_level, Opt_err, };
@@ -201,6 +203,7 @@ static const match_table_t tokens = { {Opt_noacl, "noacl"}, {Opt_usrquota, "usrquota"}, {Opt_grpquota, "grpquota"}, + {Opt_resv_level, "resv_level=%u"}, {Opt_err, NULL} };
@@ -1026,6 +1029,7 @@ static int ocfs2_fill_super(struct super_block *sb, void *data, int silent) osb->osb_commit_interval = parsed_options.commit_interval; osb->local_alloc_default_bits =ocfs2_megabytes_to_clusters (sb, parsed_options.localalloc_opt); osb->local_alloc_bits = osb->local_alloc_default_bits; + osb->osb_resv_level = parsed_options.resv_level; status =ocfs2_verify_userspace_stack (osb, &parsed_options);if (status)
@@ -1286,6 +1290,7 @@ static int ocfs2_parse_options(struct super_block *sb, mopt->slot =OCFS2_INVALID_SLOT ; mopt->localalloc_opt =OCFS2_DEFAULT_LOCAL_ALLOC_SIZE ; mopt->cluster_stack[0 ] ='\0' ; + mopt->resv_level =OCFS2_DEFAULT_RESV_LEVEL ;if (!options) { status =1 ;
@@ -1429,6 +1434,17 @@ static int ocfs2_parse_options(struct super_block *sb, mopt->mount_opt |=OCFS2_MOUNT_NO_POSIX_ACL ; mopt->mount_opt &= ~OCFS2_MOUNT_POSIX_ACL ;break ; +case Opt_resv_level: +if (is_remount) +break ; +if (match_int (&args[0 ], &option)) { + status =0 ; + goto bail; + } +if (option >=OCFS2_MIN_RESV_LEVEL && + option <OCFS2_MAX_RESV_LEVEL ) + mopt->resv_level = option; +break ;default :mlog (ML_ERROR , "Unrecognized mount option \"%s\" "
@@ -1510,6 +1526,9 @@ static int ocfs2_show_options(struct seq_file *s, struct vfsmount *mnt)else seq_printf (s,",noacl" ); +if (osb->osb_resv_level !=OCFS2_DEFAULT_RESV_LEVEL ) +seq_printf (s,",resv_level=%d" , osb->osb_resv_level); +return 0 ; }
@@ -2038,6 +2057,12 @@ static int ocfs2_initialize_super(struct super_block *sb,init_waitqueue_head (&osb->osb_mount_event); + status =ocfs2_resmap_init (osb, &osb->osb_la_resmap); +if (status) { +mlog_errno (status); + goto bail; + } + osb->vol_label =kmalloc (OCFS2_MAX_VOL_LABEL_LEN ,GFP_KERNEL );if (!osb->vol_label) {mlog (ML_ERROR ,"unable to alloc vol label\n" );
Signature · 1 line
1.6.4.2
PATCH 1/4 ocfs2: allocation reservations
Hi Mark,
The idea is cool. Some comments inlined.
Quoted 17 lines · Mark Fasheh
This patch improves Ocfs2 allocation policy by allowing an inode to reserve a portion of the local alloc bitmap for itself. The reserved portion (allocation window) is advisory in that other allocation windows might steal it if the local alloc bitmap becomes full. Otherwise, the reservations are honored and guaranteed to be free. When the local alloc window is moved to a different portion of the bitmap, existing reservations are discarded.
Reservation windows are represented internally by a red-black tree. Within that tree, each node represents the reservation window of one inode. An LRU of active reservations is also maintained. When new data is written, we allocate it from the inodes window. When all bits in a window are exhausted, we allocate a new one as close to the previous one as possible. Should we not find free space, an existing reservation is pulled off the LRU and cannibalized.
Signed-off-by Mark Fasheh <[email protected]>
<snip>
Quoted 20 lines
fs/ocfs2/reservations.c new file +20
-0+static void ocfs2_check_resmap (struct ocfs2_reservation_map *resmap) +{ +unsigned int off =0 ; +int i =0 ; +struct rb_node *node; +struct ocfs2_alloc_reservation *resv; + + node =rb_first (&resmap->m_reservations); +while (node) { + resv = rb_entry(node, struct ocfs2_alloc_reservation, r_node); + +if (i >0 && resv->r_start <= off) { +mlog (ML_ERROR ,"reservation %d has bad start off!\n" , + i); + goto bad; + } + +if (resv->r_len ==0 ) { +mlog (ML_ERROR ,"reservation %d has no length!\n" , + i);
fs/ocfs2/reservations.c line 166
Quoted 10 lines
fs/ocfs2/reservations.c new file +10
-0+ goto bad; + } + +if (resv->r_start >ocfs2_resv_end (resv)) { +mlog (ML_ERROR ,"reservation %d has invalid range!\n" , + i); + goto bad; + } + +if (ocfs2_resv_end (resv) > resmap->m_bitmap_len) {
I guess here should be ocfs2_resv_end(resv) >= resmap->m_bitmap_len?
Quoted 19 lines
fs/ocfs2/reservations.c new file +19
-0+mlog (ML_ERROR ,"reservation %d extends past bitmap!\n" , + i); + goto bad; + } + +if (ocfs2_validate_resmap_bits (resmap, i, resv)) + goto bad; + + off =ocfs2_resv_end (resv); + node =rb_next (node); + + i++; + } +return ; + +bad: +ocfs2_dump_resv (resmap); +BUG (); +}
<snip>
Quoted 16 lines
fs/ocfs2/reservations.c new file +16
-0+static void ocfs2_resv_insert (struct ocfs2_reservation_map *resmap, +struct ocfs2_alloc_reservation *new) +{ +struct rb_root *root = &resmap->m_reservations; +struct rb_node *parent =NULL ; +struct rb_node **p = &root->rb_node; +struct ocfs2_alloc_reservation *tmp; + +assert_spin_locked (&resv_lock); + +mlog (0 ,"Insert reservation start: %u len: %u\n" , new->r_start, + new->r_len); + +while (*p) { + parent = *p; +
fs/ocfs2/reservations.c line 325
Quoted 10 lines
fs/ocfs2/reservations.c new file +10
-0+ tmp = rb_entry(parent, struct ocfs2_alloc_reservation, r_node); + +if (new->r_start < tmp->r_start) + p = &(*p)->rb_left; +else if (new->r_start >ocfs2_resv_end (tmp)) + p = &(*p)->rb_right; +else { +/* This should never happen! */ +mlog (ML_ERROR ,"Duplicate reservation window!\n" ); +BUG ();
We bug out here in case r_start is in [tmp->r_start, ocfs2_resv_end(tmp)]. Do we need to check ocfs2_resv_end(new) somewhere?
Quoted 11 lines
fs/ocfs2/reservations.c new file +11
-0+ } + } + +rb_link_node (&new->r_node, parent, p); +rb_insert_color (&new->r_node, root); + new->r_inuse =1 ; + +ocfs2_resv_mark_lru (resmap, new); + +ocfs2_check_resmap (resmap); +}
<snip>
Quoted 3 lines
fs/ocfs2/reservations.c new file +3
-0+static void __ocfs2_resv_find_window (struct ocfs2_reservation_map *resmap, +struct ocfs2_alloc_reservation *resv, +unsigned int goal,unsigned int wanted)
<snip>
Quoted 17 lines
fs/ocfs2/reservations.c new file +17
-0+{ +/* Now we do a linear search for a window, starting at 'prev_rsv' */ +while (1 ) { + next =rb_next (prev); +if (next) { +mlog (0 ,"One more resv found in linear search\n" ); + next_resv =rb_entry (next, + struct ocfs2_alloc_reservation, + r_node); + + gap_start =ocfs2_resv_end (prev_resv) +1 ; + gap_end = next_resv->r_start -1 ; + gap_len = gap_end - gap_start +1 ; + }else { +mlog (0 ,"No next node\n" ); +/* +* We're at the rightmost edge of the
fs/ocfs2/reservations.c line 651
Quoted 10 lines
fs/ocfs2/reservations.c new file +10
-0+* tree. See if a reservation between this +* window and the end of the bitmap will work. +*/ + gap_start =ocfs2_resv_end (prev_resv) +1 ; + gap_len = resmap->m_bitmap_len - gap_start; + gap_end = resmap->m_bitmap_len -1 ; + } + + clen =ocfs2_resmap_find_free_bits (resmap, wanted, gap_start, + gap_len, &cstart, &clen);
I guess we can have some improvement here? In case gap_len <= best_len, we don't need to call this function actually and just loop to the next round.
Quoted 28 lines
fs/ocfs2/reservations.c new file +28
-0+if (clen == wanted) { + best_len = clen; + best_start = cstart; + goto out_insert; + }else if (clen > best_len) { + best_len = clen; + best_start = cstart; + } + +if (!next) +break ; + + prev = next; + prev_resv = rb_entry(prev, struct ocfs2_alloc_reservation, + r_node); + } + +out_insert: +if (best_len) { + resv->r_start = best_start; + resv->r_len = best_len; +ocfs2_resv_insert (resmap, resv); + } +} +static void ocfs2_cannibalize_resv (struct ocfs2_reservation_map *resmap, +struct ocfs2_alloc_reservation *resv, +unsigned int wanted) +{
<snip>
fs/ocfs2/reservations.c line 725
Quoted 6 lines
fs/ocfs2/reservations.c new file +6
-0+ }else { +unsigned int shrink = lru_resv->r_len /2 ; + +mlog (0 ,"shrink lru resv by %u\n" , shrink); + + lru_resv->r_len -= shrink;
Do we need to change lru_resv->r_last_len here so that the next search can start right after the shrinked zone? I am not sure.
Quoted 5 lines
fs/ocfs2/reservations.c new file +5
-0+ + resv->r_start =ocfs2_resv_end (lru_resv) +1 ; + resv->r_len = shrink; + } +
<snip>
Quoted 14 lines
fs/ocfs2/reservations.c new file +14
-0+void ocfs2_resmap_claimed_bits (struct ocfs2_reservation_map *resmap, +struct ocfs2_alloc_reservation *resv, +u32 cstart,u32 clen) +{ +unsigned int cend = cstart + clen -1 ; +int search, used_resv =0 ; + +if (resmap ==NULL ||ocfs2_resmap_disabled (resmap)) +return ; + +if (resv ==NULL ) +return ; + +spin_lock (&resv_lock);
fs/ocfs2/reservations.c line 886
Quoted 10 lines
fs/ocfs2/reservations.c new file +10
-0+ +mlog (0 ,"claim bits: cstart: %u cend: %u clen: %u r_start: %u " +"r_end: %u r_len: %u, r_last_start: %u r_last_len: %u\n" , + cstart, cend, clen, resv->r_start,ocfs2_resv_end (resv), + resv->r_len, resv->r_last_start, resv->r_last_len); + +/* +* Find all reservations which contain (cstart-clen). This +* could potentially be multiple ones, depending on the +* allocation.
I am just curious how this could happen with multiple reservations. ;)
Quoted 20 lines
fs/ocfs2/reservations.c new file +20
-0+* +* Each one needs to be adjusted. If the allocation overwrites +* the whole window, we should just discard that reservation. +* +* If we hit the one passed in ('resv'), we treat it slightly +* special by trying to extend it after adjustments have been +* made. +*/ + + search = cstart; +while (search <= cend) { +struct ocfs2_alloc_reservation *r; +int inc; + +/* +* This will find us the leftmost resv containing any +* bits between 'search' and 'cend' +*/ + r =ocfs2_find_resv_containing (resmap, search, cend); +if (!r)
fs/ocfs2/reservations.c line 916
Quoted 10 lines
fs/ocfs2/reservations.c new file +10
-0+break ; + + inc =ocfs2_adjust_resv_from_alloc (resmap, r, search, cend); + +/* +* This will signal the next set of code that 'resv' +* was used at least partially by the allocation. +*/ +if (r == resv) { + used_resv =1 ;
I just found that used_resv isn't used anymore later.
Quoted 14 lines
fs/ocfs2/reservations.c new file +14
-0+ resv->r_last_start = search; + resv->r_last_len = inc; + +/* +* May have been discarded above from +* ocfs2_adjust_resv_from_alloc(). +*/ +if (!ocfs2_resv_empty (resv)) +ocfs2_resv_mark_lru (resmap, resv); + } + + search += inc; + } +
<snip>
Quoted 5 lines
fs/ocfs2/reservations.h new file +5
-0+struct ocfs2_reservation_map { +struct rb_root m_reservations; +char *m_disk_bitmap; + +struct ocfs2_super *m_osb;
fs/ocfs2/reservations.h line 63
Quoted 10 lines
fs/ocfs2/reservations.h new file +10
-0+ +/* The following are not initialized to meaningful values until a disk +* bitmap is provided. */ +u32 m_bitmap_len;/* Number of valid +* bits available */ + +unsigned int m_search_start;/* Records the end +* location of our +* most recent +* allocation. */
oh, this member isn't used actually.
Quoted 5 lines
fs/ocfs2/reservations.h new file +5
-0+ +struct list_head m_lru;/* LRU of reservations +* structures. */ + +};
<snip>
Quoted 4 lines
fs/ocfs2/super.c +0
-0@@ -1429,6 +1434,17 @@ static int ocfs2_parse_options(struct super_block *sb, mopt->mount_opt |=OCFS2_MOUNT_NO_POSIX_ACL ; mopt->mount_opt &= ~OCFS2_MOUNT_POSIX_ACL ;break ;
fs/ocfs2/super.c static int ocfs2_parse_options(struct super_block *sb, · line 1446
Quoted 10 lines
fs/ocfs2/super.c +10
-0+case Opt_resv_level: +if (is_remount) +break ; +if (match_int (&args[0 ], &option)) { + status =0 ; + goto bail; + } +if (option >=OCFS2_MIN_RESV_LEVEL && + option <OCFS2_MAX_RESV_LEVEL ) + mopt->resv_level = option;
Do we need to check cluster size here? I guess with a large cluster size, say 1M, we need a very small window or even no window. ok, that's all for the codes.
Besides the comments, I have some other thoughts.
1. Do we need to some additional check in ocfs2_reserve_local_alloc_bits? The old schema just check the condition bits_wanted <= free_bits since local_alloc is contiguous enough. But with reservation window, we can have a fragmented local alloc actually.
2. Current codes don't handle with space reservations(unwritten extents). Maybe it is because unwritten will allocate contiguous clusters?
With these 2 problems, I corrupted the system somehow by the following scripts(Sorry, Mark, ;) ).
echo 'y'|mkfs.ocfs2 -b 4K -C 4K --fs-features=local $DEVICE mount -t ocfs2 $DEVICE $MNT_DIR for((j=0;j<32;j++))
do
FILE_NAME=$MNT_DIR/$RANDOM
for((i=0;i<63;i++))
do
cat /mnt/4096 >> $FILE_NAME #4096 is a file with 4096 bytes.
donedone
FILE_NAME=$MNT_DIR/$RANDOM
./rw_test -f $FILE_NAME -l 0 -u 8192 #this will create a file with an unwritten extent of 2 clusters length at offset 0.
umount $MNT_DIR
Now run fsck.ocfs2, you will find duplicated clusters. This is caused by the code here.
Quoted 5 lines
(quoted diff) +0
-0start = ocfs2_local_alloc_find_clear_bits(osb, alloc, bits_wanted, ac->ac_resv); if (start == -1) { /* TODO: Shouldn't we just BUG here? */ status = -ENOSPC;
Review static int ocfs2_parse_options(struct super_block *sb,
Quoted 10 lines
(quoted diff) +0
-0mlog_errno(status); goto bail; } printk("end of start %d\n", start); bitmap = la->la_bitmap; *bit_off = le32_to_cpu(la->la_bm_off) + start; /* local alloc is always contiguous by nature -- we never * delete bits from it! */ *num_bits = bits_wanted;
See here? bit_wanted is 2, while with the script, the local alloc is divided into 32 parts and every part only have 1 clusters left. But this code deem that we can always get bits_wanted. :)
Regards,
Tao
PATCH 1/4 ocfs2: allocation reservations
Quoted 2 lines · Tao Ma
Hi Mark,
The idea is cool. Some comments inlined.
Thanks, and thanks for the detailed review.
Quoted 23 lines
Quoted 23 lines
fs/ocfs2/reservations.c new file +23
-0+static void ocfs2_check_resmap (struct ocfs2_reservation_map *resmap) +{ +unsigned int off =0 ; +int i =0 ; +struct rb_node *node; +struct ocfs2_alloc_reservation *resv; + + node =rb_first (&resmap->m_reservations); +while (node) { + resv = rb_entry(node, struct ocfs2_alloc_reservation, r_node); + +if (i >0 && resv->r_start <= off) { +mlog (ML_ERROR ,"reservation %d has bad start off!\n" , + i); + goto bad; + } + +if (resv->r_len ==0 ) { +mlog (ML_ERROR ,"reservation %d has no length!\n" , + i); + goto bad; + } +
Quoted 8 lines
fs/ocfs2/reservations.c line 166
Quoted 7 lines
fs/ocfs2/reservations.c new file +7
-0+if (resv->r_start >ocfs2_resv_end (resv)) { +mlog (ML_ERROR ,"reservation %d has invalid range!\n" , + i); + goto bad; + } + +if (ocfs2_resv_end (resv) > resmap->m_bitmap_len) {I guess here should be
ocfs2_resv_end(resv)>=resmap->m_bitmap_len?
Yes, good catch. I'll fix that up.
Quoted 20 lines
Quoted 20 lines
fs/ocfs2/reservations.c new file +20
-0+static void ocfs2_resv_insert (struct ocfs2_reservation_map *resmap, +struct ocfs2_alloc_reservation *new) +{ +struct rb_root *root = &resmap->m_reservations; +struct rb_node *parent =NULL ; +struct rb_node **p = &root->rb_node; +struct ocfs2_alloc_reservation *tmp; + +assert_spin_locked (&resv_lock); + +mlog (0 ,"Insert reservation start: %u len: %u\n" , new->r_start, + new->r_len); + +while (*p) { + parent = *p; + + tmp = rb_entry(parent, struct ocfs2_alloc_reservation, r_node); + +if (new->r_start < tmp->r_start) + p = &(*p)->rb_left;
Quoted 8 lines
fs/ocfs2/reservations.c line 325
Quoted 6 lines
fs/ocfs2/reservations.c new file +6
-0+else if (new->r_start >ocfs2_resv_end (tmp)) + p = &(*p)->rb_right; +else { +/* This should never happen! */ +mlog (ML_ERROR ,"Duplicate reservation window!\n" ); +BUG ();We bug out here in case
r_startis in [tmp->r_start,ocfs2_resv_end(tmp)]. Do we need to checkocfs2_resv_end(new)somewhere?
We don't really care about ocfs2_resv_end(new) for tree traversal purposes. However, I think you have a good idea - reservations should never overlap, and this would be a good place to check for code bugs. I'll add some extra checks.
Quoted 22 lines
Quoted 22 lines
fs/ocfs2/reservations.c new file +22
-0+{ +/* Now we do a linear search for a window, starting at 'prev_rsv' */ +while (1 ) { + next =rb_next (prev); +if (next) { +mlog (0 ,"One more resv found in linear search\n" ); + next_resv =rb_entry (next, + struct ocfs2_alloc_reservation, + r_node); + + gap_start =ocfs2_resv_end (prev_resv) +1 ; + gap_end = next_resv->r_start -1 ; + gap_len = gap_end - gap_start +1 ; + }else { +mlog (0 ,"No next node\n" ); +/* +* We're at the rightmost edge of the +* tree. See if a reservation between this +* window and the end of the bitmap will work. +*/ + gap_start =ocfs2_resv_end (prev_resv) +1 ; + gap_len = resmap->m_bitmap_len - gap_start;
Quoted 8 lines
fs/ocfs2/reservations.c line 651
Quoted 5 lines
fs/ocfs2/reservations.c new file +5
-0+ gap_end = resmap->m_bitmap_len -1 ; + } + + clen =ocfs2_resmap_find_free_bits (resmap, wanted, gap_start, + gap_len, &cstart, &clen);I guess we can have some improvement here? In case
gap_len<=best_len, we don't need to call this function actually and just loop to the next round.
Yep, fixed. That should save us some CPU :)
Quoted 29 lines
Quoted 28 lines
fs/ocfs2/reservations.c new file +28
-0+if (clen == wanted) { + best_len = clen; + best_start = cstart; + goto out_insert; + }else if (clen > best_len) { + best_len = clen; + best_start = cstart; + } + +if (!next) +break ; + + prev = next; + prev_resv = rb_entry(prev, struct ocfs2_alloc_reservation, + r_node); + } + +out_insert: +if (best_len) { + resv->r_start = best_start; + resv->r_len = best_len; +ocfs2_resv_insert (resmap, resv); + } +} +static void ocfs2_cannibalize_resv (struct ocfs2_reservation_map *resmap, +struct ocfs2_alloc_reservation *resv, +unsigned int wanted) +{<snip>
Quoted 8 lines
fs/ocfs2/reservations.c line 725
Quoted 6 lines
fs/ocfs2/reservations.c new file +6
-0+ }else { +unsigned int shrink = lru_resv->r_len /2 ; + +mlog (0 ,"shrink lru resv by %u\n" , shrink); + + lru_resv->r_len -= shrink;Do we need to change
lru_resv->r_last_lenhere so that the next search can start right after the shrinked zone? I am not sure.
No, I left them unchanged on purpose - they still record the last sucessful allocation. In theory we could try adjusting them, but that'd be speculative and not based on any actual allocation requests.
Quoted 23 lines
Quoted 5 lines
fs/ocfs2/reservations.c new file +5
-0+ + resv->r_start =ocfs2_resv_end (lru_resv) +1 ; + resv->r_len = shrink; + } +<snip>
Quoted 17 lines
fs/ocfs2/reservations.c new file +17
-0+void ocfs2_resmap_claimed_bits (struct ocfs2_reservation_map *resmap, +struct ocfs2_alloc_reservation *resv, +u32 cstart,u32 clen) +{ +unsigned int cend = cstart + clen -1 ; +int search, used_resv =0 ; + +if (resmap ==NULL ||ocfs2_resmap_disabled (resmap)) +return ; + +if (resv ==NULL ) +return ; + +spin_lock (&resv_lock); + + mlog(0, "claim bits: cstart: %u cend: %u clen: %u r_start: %u " + "r_end: %u r_len: %u, r_last_start: %u r_last_len: %u\n",
Quoted 8 lines
fs/ocfs2/reservations.c line 886
Quoted 7 lines
fs/ocfs2/reservations.c new file +7
-0+ cstart, cend, clen, resv->r_start,ocfs2_resv_end (resv), + resv->r_len, resv->r_last_start, resv->r_last_len); + +/* +* Find all reservations which contain (cstart-clen). This +* could potentially be multiple ones, depending on the +* allocation. I am just curious how this could happen with multiple reservations. ;)
Yeah, I realized after I sent the series -- this is old code that I'm going to remove in my next round. It's back from when local alloc didn't always honor reservations (which as I discussed, didn't work well). The only parts of this whole loop that we need to keep is a call to ocfs2_adjust_resv_from_alloc() for the passed in reservation.
Quoted 23 lines
Quoted 23 lines
fs/ocfs2/reservations.c new file +23
-0+* +* Each one needs to be adjusted. If the allocation overwrites +* the whole window, we should just discard that reservation. +* +* If we hit the one passed in ('resv'), we treat it slightly +* special by trying to extend it after adjustments have been +* made. +*/ + + search = cstart; +while (search <= cend) { +struct ocfs2_alloc_reservation *r; +int inc; + +/* +* This will find us the leftmost resv containing any +* bits between 'search' and 'cend' +*/ + r =ocfs2_find_resv_containing (resmap, search, cend); +if (!r) +break ; + + inc =ocfs2_adjust_resv_from_alloc (resmap, r, search, cend);
Quoted 8 lines
fs/ocfs2/reservations.c line 916
Quoted 7 lines
fs/ocfs2/reservations.c new file +7
-0+ +/* +* This will signal the next set of code that 'resv' +* was used at least partially by the allocation. +*/ +if (r == resv) { + used_resv =1 ;I just found that
used_resvisn't used anymore later.
Yep, this will go away as mentioned.
Quoted 8 lines
Quoted 8 lines
fs/ocfs2/reservations.h new file +8
-0+struct ocfs2_reservation_map { +struct rb_root m_reservations; +char *m_disk_bitmap; + +struct ocfs2_super *m_osb; + +/* The following are not initialized to meaningful values until a disk +* bitmap is provided. */
Quoted 8 lines
fs/ocfs2/reservations.h line 63
Quoted 7 lines
fs/ocfs2/reservations.h new file +7
-0+u32 m_bitmap_len;/* Number of valid +* bits available */ + +unsigned int m_search_start;/* Records the end +* location of our +* most recent +* allocation. */ oh, this member isn't used actually.
Yeah another bit of old code. I'll remove.
Quoted 68 lines
Quoted 5 lines
fs/ocfs2/reservations.h new file +5
-0+ +struct list_head m_lru;/* LRU of reservations +* structures. */ + +};<snip>
Quoted 4 lines
fs/ocfs2/super.c +0
-0@@ -1429,6 +1434,17 @@ static int ocfs2_parse_options(struct super_block *sb, mopt->mount_opt |=OCFS2_MOUNT_NO_POSIX_ACL ; mopt->mount_opt &= ~OCFS2_MOUNT_POSIX_ACL ;break ;fs/ocfs2/super.c static int ocfs2_parse_options(struct super_block *sb, · line 1446
Quoted 10 lines
fs/ocfs2/super.c +10
-0+case Opt_resv_level: +if (is_remount) +break ; +if (match_int (&args[0 ], &option)) { + status =0 ; + goto bail; + } +if (option >=OCFS2_MIN_RESV_LEVEL && + option <OCFS2_MAX_RESV_LEVEL ) + mopt->resv_level = option;Do we need to check cluster size here? I guess with a large cluster size, say 1M, we need a very small window or even no window. ok, that's all for the codes.
Besides the comments, I have some other thoughts.
1. Do we need to some additional check inocfs2_reserve_local_alloc_bits? The old schema just check the conditionbits_wanted<=free_bitssincelocal_allocis contiguous enough. But with reservation window, we can have a fragmented local alloc actually.
2. Current codes don't handle with space reservations(unwritten extents). Maybe it is because unwritten will allocate contiguous clusters?With these 2 problems, I corrupted the system somehow by the following
scripts(Sorry, Mark, ;)).echo 'y'|mkfs.ocfs2 -b 4K -C 4K --fs-features=local $DEVICE mount -t ocfs2 $DEVICE $MNT_DIR for((j=0;j<32;j++))
doFILE_NAME=$MNT_DIR/$RANDOM for((i=0;i<63;i++)) do cat /mnt/4096 >> $FILE_NAME #4096 is a file with 4096 bytes. donedone
FILE_NAME=$MNT_DIR/$RANDOM
./rw_test -f $FILE_NAME -l 0 -u 8192 #this will create a file with an unwritten extent of 2 clusters length at offset 0.
umount $MNT_DIRNow run fsck.ocfs2, you will find duplicated clusters. This is caused by the code here.
Quoted 5 lines
(quoted diff) +0
-0start = ocfs2_local_alloc_find_clear_bits(osb, alloc, bits_wanted, ac->ac_resv); if (start == -1) { /* TODO: Shouldn't we just BUG here? */ status = -ENOSPC;Review static int ocfs2_parse_options(struct super_block *sb,
Quoted 10 lines
(quoted diff) +0
-0mlog_errno(status); goto bail; } printk("end of start %d\n", start); bitmap = la->la_bitmap; *bit_off = le32_to_cpu(la->la_bm_off) + start; /* local alloc is always contiguous by nature -- we never * delete bits from it! */ *num_bits = bits_wanted;
Quoted 3 lines
See here?
bit_wantedis 2, while with the script, the local alloc is divided into 32 parts and every part only have 1 clusters left. But this code deem that we can always getbits_wanted. :)
Ahh, yeah we need to pass back the actual allocation from ocfs2_local_alloc_find_clear_bits(). That should be simple enough. I probably never hit this because all other allocations that went to the local alloc were 1 bit at a time (for file write, etc).
Btw, I realized that we don't really need ocfs2_local_alloc_in_range() since we don't allocate inode groups from it any more. Or at least, I can simplify it quite a bit.
--Mark
--
Mark Fasheh
PATCH 1/4 ocfs2: allocation reservations
Hi Mark,
Quoted 17 lines · Mark Fasheh
Quoted 2 lines · Tao Ma
Hi Mark,
The idea is cool. Some comments inlined.Thanks, and thanks for the detailed review.
Quoted 9 lines
<snip>
fs/ocfs2/reservations.c line 725
Quoted 6 lines
fs/ocfs2/reservations.c new file +6
-0+ }else { +unsigned int shrink = lru_resv->r_len /2 ; + +mlog (0 ,"shrink lru resv by %u\n" , shrink); + + lru_resv->r_len -= shrink;Do we need to change
lru_resv->r_last_lenhere so that the next search can start right after the shrinked zone? I am not sure.
Quoted 3 lines
No, I left them unchanged on purpose - they still record the last sucessful allocation. In theory we could try adjusting them, but that'd be speculative and not based on any actual allocation requests.
oh, thanks for the explanation.
<snip>
Quoted 44 lines
Quoted 44 lines
Besides the comments, I have some other thoughts.
1. Do we need to some additional check inocfs2_reserve_local_alloc_bits? The old schema just check the conditionbits_wanted<=free_bitssincelocal_allocis contiguous enough. But with reservation window, we can have a fragmented local alloc actually.
2. Current codes don't handle with space reservations(unwritten extents). Maybe it is because unwritten will allocate contiguous clusters?With these 2 problems, I corrupted the system somehow by the following
scripts(Sorry, Mark, ;)).echo 'y'|mkfs.ocfs2 -b 4K -C 4K --fs-features=local $DEVICE mount -t ocfs2 $DEVICE $MNT_DIR for((j=0;j<32;j++))
doFILE_NAME=$MNT_DIR/$RANDOM for((i=0;i<63;i++)) do cat /mnt/4096 >> $FILE_NAME #4096 is a file with 4096 bytes. donedone
FILE_NAME=$MNT_DIR/$RANDOM
./rw_test -f $FILE_NAME -l 0 -u 8192 #this will create a file with an unwritten extent of 2 clusters length at offset 0.
umount $MNT_DIRNow run fsck.ocfs2, you will find duplicated clusters. This is caused by the code here.
Quoted 15 lines
start = ocfs2_local_alloc_find_clear_bits(osb, alloc, bits_wanted, ac->ac_resv); if (start == -1) { /* TODO: Shouldn't we just BUG here? */ status = -ENOSPC; mlog_errno(status); goto bail; } printk("end of start %d\n", start); bitmap = la->la_bitmap; *bit_off = le32_to_cpu(la->la_bm_off) + start; /* local alloc is always contiguous by nature -- we never * delete bits from it! */ *num_bits = bits_wanted;
Quoted 8 lines
Quoted 3 lines
See here?
bit_wantedis 2, while with the script, the local alloc is divided into 32 parts and every part only have 1 clusters left. But this code deem that we can always getbits_wanted. :)Ahh, yeah we need to pass back the actual allocation from
ocfs2_local_alloc_find_clear_bits(). That should be simple enough. I probably never hit this because all other allocations that went to the local alloc were 1 bit at a time (for file write, etc).
yeah except unwritten extents. :)
Quoted 5 lines
Btw, I realized that we don't really need
ocfs2_local_alloc_in_range()since we don't allocate inode groups from it any more. Or at least, I can simplify it quite a bit.
yeah, actually I thought of this when reviewing the patch. But maybe we need another ac_max_blocks in the future. Who knows? ;)
I guess currently we can just check bm_off+bg_bits and it is ok for us now. And also we can clean your ocfs2_local_alloc_find_clear_bits since now we have no chance of a local_resv which only is used for ocfs2_local_alloc_in_range now. ;)
Regards,
Tao
PATCH 2/4 ocfs2: use allocation reservations during file write
In reply to Mark FashehAdd a per-inode reservations structure and pass it through to the reservations code.
--- fs/ocfs2/alloc.c | 2 ++ fs/ocfs2/aops.c | 2 ++ fs/ocfs2/file.c | 3 +++ fs/ocfs2/inode.c | 4 ++++ fs/ocfs2/inode.h | 2 ++ fs/ocfs2/super.c | 2 ++ 6 files changed, 15 insertions(+), 0 deletions(-)
fs/ocfs2/alloc.c +2 -0
@@ -7307,6 +7307,8 @@ int ocfs2_convert_inline_data_to_extents(struct inode *inode, } did_quota =1 ; + data_ac->ac_resv = &OCFS2_I (inode)->ip_la_data_resv; + ret =ocfs2_claim_clusters (osb, handle, data_ac,1 , &bit_off, &num);if (ret) {
fs/ocfs2/aops.c +2 -0
@@ -1734,6 +1734,8 @@ int ocfs2_write_begin_nolock(struct address_space *mapping, goto out; } + data_ac->ac_resv = &OCFS2_I (inode)->ip_la_data_resv; + credits =ocfs2_calc_extend_credits (inode->i_sb, &di->id2.i_list, clusters_to_alloc);
fs/ocfs2/file.c +3 -0
@@ -485,6 +485,9 @@ static int ocfs2_truncate_file(struct inode *inode,down_write (&OCFS2_I (inode)->ip_alloc_sem); +ocfs2_resv_discard (&osb->osb_la_resmap, + &OCFS2_I (inode)->ip_la_data_resv); +/* * The inode lock forced other nodes to sync and drop their * pages, which (correctly) happens even if we have a truncate
fs/ocfs2/inode.c +4 -0
@@ -1097,6 +1097,10 @@ void ocfs2_clear_inode(struct inode *inode)ocfs2_mark_lockres_freeing (&oi->ip_inode_lockres);ocfs2_mark_lockres_freeing (&oi->ip_open_lockres); +ocfs2_resv_discard (&OCFS2_SB (inode->i_sb)->osb_la_resmap, + &oi->ip_la_data_resv); +ocfs2_resv_init_once (&oi->ip_la_data_resv); +/* We very well may get a clear_inode before all an inodes * metadata has hit disk. Of course, we can't drop any cluster * locks until the journal has finished with it. The only
fs/ocfs2/inode.h +2 -0
@@ -70,6 +70,8 @@ struct ocfs2_inode_info/* Only valid if the inode is the dir. */ u32 ip_last_used_slot;u64 ip_last_used_group; + +struct ocfs2_alloc_reservation ip_la_data_resv; };/*
fs/ocfs2/super.c +2 -0
@@ -1703,6 +1703,8 @@ static void ocfs2_inode_init_once(void *data) oi->ip_blkno =0ULL ; oi->ip_clusters =0 ; +ocfs2_resv_init_once (&oi->ip_la_data_resv); +ocfs2_lock_res_init_once (&oi->ip_rw_lockres);ocfs2_lock_res_init_once (&oi->ip_inode_lockres);ocfs2_lock_res_init_once (&oi->ip_open_lockres);
Signature · 1 line
1.6.4.2
PATCH 2/4 ocfs2: use allocation reservations during file write
Hi Mark,
Quoted 12 lines · Mark Fasheh
Add a per-inode reservations structure and pass it through to the reservations code.
Signed-off-by Mark Fasheh <[email protected]>--- fs/ocfs2/alloc.c | 2 ++ fs/ocfs2/aops.c | 2 ++ fs/ocfs2/file.c | 3 +++ fs/ocfs2/inode.c | 4 ++++ fs/ocfs2/inode.h | 2 ++ fs/ocfs2/super.c | 2 ++ 6 files changed, 15 insertions(+), 0 deletions(-)
<snip>
fs/ocfs2/aops.c int ocfs2_write_begin_nolock(struct address_space *mapping, · line 1738
Quoted 11 lines
fs/ocfs2/aops.c +2
-0@@ -1734,6 +1734,8 @@ int ocfs2_write_begin_nolock(struct address_space *mapping, goto out; } + data_ac->ac_resv = &OCFS2_I (inode)->ip_la_data_resv; +
Here is a bug. In case, we are writing the unwritten extents, we don't have a valid data_ac.
fs/ocfs2/aops.c int ocfs2_write_begin_nolock(struct address_space *mapping, · line 1741
Quoted 3 lines
fs/ocfs2/aops.c +0
-0credits =ocfs2_calc_extend_credits (inode->i_sb, &di->id2.i_list, clusters_to_alloc);
Regards,
Tao
PATCH 3/4 ocfs2: use allocation reservations for directory data
In reply to Mark FashehUse the reservations system for unindexed dir tree allocations. We don't bother with the indexed tree as reads from it are mostly random anyway. By default this behavior is turned off and can be turned on via mount option 'dir_resv'. Workloads which create many large directories will want to turn it on.
A future improvement will be to use a different window size for directory inodes. Once done, we should change the default for this feature to be enabled.
--- Documentation/filesystems/ocfs2.txt | 2 ++ fs/ocfs2/dir.c | 4 ++++ fs/ocfs2/ocfs2.h | 2 ++ fs/ocfs2/suballoc.c | 1 + fs/ocfs2/super.c | 15 +++++++++++++++ 5 files changed, 24 insertions(+), 0 deletions(-)
Documentation/filesystems/ocfs2.txt +2 -0
@@ -83,3 +83,5 @@ noacl (*) Disables POSIX Access Control Lists support. resv_level=4 (*) Set how agressive allocation reservations will be. Valid values are between 0 (reservations off) to 8 (maximum space for reservations). +no_dir_resv (*) Don't get allocation reservations on directory inodes. +dir_resv Get allocation reservations on directory inodes.
fs/ocfs2/dir.c +4 -0
@@ -2993,6 +2993,8 @@ static int ocfs2_expand_inline_dir(struct inode *dir, struct buffer_head *di_bh,* if we only get one now, that's enough to continue. The rest * will be claimed after the conversion to extents. */ +if (osb->s_mount_opt &OCFS2_MOUNT_DIR_RESV ) + data_ac->ac_resv = &oi->ip_la_data_resv; ret =ocfs2_claim_clusters (osb, handle, data_ac,1 , &bit_off, &len);if (ret) {mlog_errno (ret);
@@ -3371,6 +3373,8 @@ static int ocfs2_extend_dir(struct ocfs2_super *osb,mlog_errno (status); goto bail; } +if (osb->s_mount_opt &OCFS2_MOUNT_DIR_RESV ) + data_ac->ac_resv = &OCFS2_I (dir)->ip_la_data_resv; credits =ocfs2_calc_extend_credits (sb, el,1 ); }else {
fs/ocfs2/ocfs2.h +2 -0
@@ -255,6 +255,8 @@ enum ocfs2_mount_optionscontrol lists */ OCFS2_MOUNT_USRQUOTA =1 <<10 ,/* We support user quotas */ OCFS2_MOUNT_GRPQUOTA =1 <<11 ,/* We support group quotas */ + OCFS2_MOUNT_DIR_RESV = 1 << 12, /* Get reservations + * on directories */ };#define OCFS2_OSB_SOFT_RO 0x0001
fs/ocfs2/suballoc.c +1 -0
@@ -137,6 +137,7 @@ void ocfs2_free_ac_resource(struct ocfs2_alloc_context *ac) }brelse (ac->ac_bh); ac->ac_bh =NULL ; + ac->ac_resv =NULL ; }void ocfs2_free_alloc_context (struct ocfs2_alloc_context *ac)
fs/ocfs2/super.c +15 -0
@@ -177,6 +177,8 @@ enum { Opt_usrquota, Opt_grpquota, Opt_resv_level, + Opt_dir_resv, + Opt_no_dir_resv, Opt_err, };
@@ -204,6 +206,8 @@ static const match_table_t tokens = { {Opt_usrquota, "usrquota"}, {Opt_grpquota, "grpquota"}, {Opt_resv_level, "resv_level=%u"}, + {Opt_dir_resv, "dir_resv"}, + {Opt_no_dir_resv, "no_dir_resv"}, {Opt_err, NULL} };
@@ -1445,6 +1449,12 @@ static int ocfs2_parse_options(struct super_block *sb, option < OCFS2_MAX_RESV_LEVEL) mopt->resv_level = option;break ; +case Opt_dir_resv: + mopt->mount_opt |=OCFS2_MOUNT_DIR_RESV ; +break ; +case Opt_no_dir_resv: + mopt->mount_opt &= ~OCFS2_MOUNT_DIR_RESV ; +break ;default :mlog (ML_ERROR , "Unrecognized mount option \"%s\" "
@@ -1529,6 +1539,11 @@ static int ocfs2_show_options(struct seq_file *s, struct vfsmount *mnt)if (osb->osb_resv_level !=OCFS2_DEFAULT_RESV_LEVEL )seq_printf (s,",resv_level=%d" , osb->osb_resv_level); +if (opts &OCFS2_MOUNT_DIR_RESV ) +seq_printf (s,",dir_resv" ); +else +seq_printf (s,",no_dir_resv" ); +return 0 ; }
Signature · 1 line
1.6.4.2
PATCH 4/4 ocfs2: allocate btree internal block groups from the global bitmap
In reply to Mark FashehOtherwise, the need for a very large contiguous allocation tends to wreak havoc on many inode allocation reservations on the local alloc, thus ruining any chances for contiguousness.
--- fs/ocfs2/suballoc.c | 5 ++++- 1 files changed, 4 insertions(+), 1 deletions(-)
fs/ocfs2/suballoc.c +4 -1
@@ -659,7 +659,8 @@ int ocfs2_reserve_new_metadata_blocks(struct ocfs2_super *osb, status =ocfs2_reserve_suballoc_bits (osb, (*ac),EXTENT_ALLOC_SYSTEM_INODE , - slot,NULL ,ALLOC_NEW_GROUP ); + slot,NULL , +ALLOC_GROUPS_FROM_GLOBAL |ALLOC_NEW_GROUP );if (status <0 ) {if (status != -ENOSPC )mlog_errno (status);
@@ -1821,6 +1822,8 @@ int __ocfs2_claim_clusters(struct ocfs2_super *osb, && ac->ac_which != OCFS2_AC_USE_MAIN);if (ac->ac_which ==OCFS2_AC_USE_LOCAL ) { +WARN_ON (min_clusters >1 ); + status = ocfs2_claim_local_alloc_bits(osb, handle, ac,
Signature · 1 line
1.6.4.2