The following patches(3) are one ext3 reservation bug fix and two improvements. (Note this does not include the bug fix we discussed last Friday.)
Thoughts?
Thanks,
Mingming
Before we changed the per-filesystem reservations from a linked list to a red-black tree, in order to speed up the linear search from the list head, we keep the current(stale) reservation window as a reference pointer to skip the nodes prior to the current/stale window node, when failed to allocate a new window in current group and try to do allocation in next group.
With the red-black tree change, searching from the root is fast enough so we don't need to keep the current window as a reference pointer to speed up the search.Also, keep the curret/stale window in the tree while try to allocate block in the rest groups could cause the window size being possibly doubled incorrectly: currently the hit ratio bit was not cleared until we find a new window, so when we continue to search a new window in the next group, the current/stale window hit ratio bit is checked again, and window size could be doubled again(wrong!).
This will cause too early to back to block allocation without reservation. This probably explain why we saw random write performance issue when the filesystem is really full before: for every new block in request, we do exaust the whole filesystem with wrong window size, and back to non-reservation block allocation at last.
---
linux-2.6.9-rc4-mm1-ming/fs/ext3/balloc.c | 7 +++++++
1 files changed, 7 insertions(+)
diff -puN fs/ext3/balloc.c~ext3_reservation_remove_stale_window fs/ext3/balloc.c
--- linux-2.6.9-rc4-mm1/fs/ext3/balloc.c~ext3_reservation_remove_stale_window 2004-10-18 22:26:44.108077296 -0700
+++ linux-2.6.9-rc4-mm1-ming/fs/ext3/balloc.c 2004-10-18 22:34:55.571363520 -0700
@@ -951,6 +951,13 @@ found_rsv_window:
}
return 0; /* succeed */
failed:
+ /*
+ * failed to find a new reservation window in the current
+ * group, remove the current(stale) reservation window
+ * if there is any
+ */
+ if (!rsv_is_empty(&my_rsv->rsv_window))
+ rsv_window_remove(sb, my_rsv);
return -1; /* failed */
}
_
On Mon, Oct 18, 2004 at 03:55:04PM -0700, Mingming Cao wrote:
>
> Before we changed the per-filesystem reservations from a linked list
> to a red-black tree, in order to speed up the linear search from the
> list head, we keep the current(stale) reservation window as a
> reference pointer to skip the nodes prior to the current/stale
> window node, when failed to allocate a new window in current group
> and try to do allocation in next group.
One wonders whether a prio tree of the sort used by the current VMA
searching code would be a better match to the problem than the
red-black approach.
--
Mathematics is the supreme nostalgia of our time.
On Mon, 2004-10-18 at 16:41, Matt Mackall wrote:
> On Mon, Oct 18, 2004 at 03:55:04PM -0700, Mingming Cao wrote:
> >
> > Before we changed the per-filesystem reservations from a linked list
> > to a red-black tree, in order to speed up the linear search from the
> > list head, we keep the current(stale) reservation window as a
> > reference pointer to skip the nodes prior to the current/stale
> > window node, when failed to allocate a new window in current group
> > and try to do allocation in next group.
>
> One wonders whether a prio tree of the sort used by the current VMA
> searching code would be a better match to the problem than the
> red-black approach.
Could you please elaborate more? I think the current VMA code is using
red-black tree in their searching code(find_vma()).
On Mon, Oct 18, 2004 at 06:11:16PM -0700, Mingming Cao wrote:
> On Mon, 2004-10-18 at 16:41, Matt Mackall wrote:
> > On Mon, Oct 18, 2004 at 03:55:04PM -0700, Mingming Cao wrote:
> > >
> > > Before we changed the per-filesystem reservations from a linked list
> > > to a red-black tree, in order to speed up the linear search from the
> > > list head, we keep the current(stale) reservation window as a
> > > reference pointer to skip the nodes prior to the current/stale
> > > window node, when failed to allocate a new window in current group
> > > and try to do allocation in next group.
> >
> > One wonders whether a prio tree of the sort used by the current VMA
> > searching code would be a better match to the problem than the
> > red-black approach.
>
> Could you please elaborate more? I think the current VMA code is using
> red-black tree in their searching code(find_vma()).
I was thinking of the priority search tree stuff in mm/prio_tree.c.
But on further reflection, they're not really advantageous here as the
windows in question are non-overlapping and the RB approach looks
perfectly sensible.
--
Mathematics is the supreme nostalgia of our time.