This is the third of the fs/buffer.c patches I've been working on. It
substantially improves low-memory behavior of refill_freelist; using
this patch with the get_unused_buffer_heads patch I've been able to run
simultaneous compiles of net-tools with only 100 buffer heads for the
whole system to share. (bdflush was awakened about a million times, but
everything finished successfully.)
Here's a summary of the changes:
(1) The can_reclaim routine was rolled into find_candidate, and the
unsafe refile_buffer() was removed.
(2) The test in find_candidate for locked buffers followed by setting
the count to 0 was removed. It simply isn't true that there aren't
unlocked buffers after the first locked one. I'm running a debugging
test that grooms the buffer lists every time bdflush wakes, and it
frequently reports unlocked buffers after the first locked one. (In one
case, 341 buffers!) With this test in place find_candidate was ignoring
potentially freeable buffers on the locked list.
(3) The candidate selection in refill_freelist now compares lru times at
each step; previously it compared lru times for the first set of
buffers, but then selected all subsequent ones from the same list.
(4) The buffer b_lru_time is now set only when a constructive reference
to the buffer (e.g. getblk()) is made. Previously the lru time was
being updated when refiling the buffer, which is often just an internal
bookkeeping operation. Also, to my eyes the lru time wasn't being set
at all for buffers on the locked list.
(5) The initial list is now set to BUF_CLEAN in getblk; previously
bufferes were being put on the locked list if they previously were
there.
(6) The memory goal in refill_freelist is reduced if the number of
potentially freeable buffers is small; it tries to free no more than 1/4
of the number of buffers on the clean and locked lists.
(7) A very important exit condition in refill_freelist has been added:
after trying all the resources, but before waking bdflush, return if
_any_ memory has been obtained, or if another task has freed any buffers
(free_list[isize] != NULL). Without this test it's possible to fall
into a truly pathological deadlock condition: all the tasks wanting
buffers may have entered refill_freelist, with none of them able to
reach their goal, but having jointly freed enough buffers to satisfy
everyone.
(8) After waking bdflush, the goal is set to the minimum: 1 buffer. If
this point is reached, something is very wrong with the system, and we
want to get the task out of refill_freelist if at all possible.
I'd appreciate any comments or suggestions regarding the changes.
Regards,
Bill
--------------F57AEB0F3D8654E5E3BDEF48
Content-Type: text/plain; charset=us-ascii; name="buffer_ref47-patch"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline; filename="buffer_ref47-patch"
--- fs/buffer.c.old Sat Jul 19 08:17:10 1997
+++ fs/buffer.c Mon Jul 28 14:18:25 1997
@@ -560,6 +560,7 @@
if (!bh)
return NULL;
bh->b_count++;
+ bh->b_lru_time = jiffies;
wait_on_buffer(bh);
if (bh->b_dev == dev &&
bh->b_blocknr == block &&
@@ -642,34 +643,20 @@
}
}
-/* Check if a buffer is OK to be reclaimed. */
-static inline int can_reclaim(struct buffer_head *bh, int size)
-{
- if (bh->b_count ||
- buffer_protected(bh) ||
- buffer_locked(bh))
- return 0;
-
- if (buffer_dirty(bh)) {
- refile_buffer(bh);
- return 0;
- }
-
- if (bh->b_size != size)
- return 0;
-
- return 1;
-}
-
-/* Find a candidate buffer to be reclaimed. */
-static struct buffer_head *find_candidate(struct buffer_head *list,
+/*
+ * Find a candidate buffer to be reclaimed.
+ * N.B. Must search the entire BUF_LOCKED list rather than terminating
+ * when the first locked buffer is found. Buffers are unlocked at
+ * completion of IO, and under some conditions there may be (many)
+ * unlocked buffers after the first locked one.
+ */
+static struct buffer_head *find_candidate(struct buffer_head *bh,
int *list_len, int size)
{
- struct buffer_head *bh;
-
- for (bh = list;
- bh && (*list_len) > 0;
- bh = bh->b_next_free, (*list_len)--) {
+ if (!bh)
+ goto no_candidate;
+
+ for (; (*list_len) > 0; bh = bh->b_next_free, (*list_len)--) {
if (size != bh->b_size) {
/* This provides a mechanism for freeing blocks
* of other sizes, this is necessary now that we
@@ -680,110 +667,144 @@
break;
continue;
}
-
- if (buffer_locked(bh) && bh->b_list == BUF_LOCKED) {
- /* Buffers are written in the order they are placed
- * on the locked list. If we encounter a locked
- * buffer here, this means that the rest of them
- * are also locked.
- */
- (*list_len) = 0;
- return NULL;
- }
-
- if (can_reclaim(bh,size))
- return bh;
+ else if (!bh->b_count &&
+ !buffer_locked(bh) &&
+ !buffer_protected(bh) &&
+ !buffer_dirty(bh))
+ return bh;
}
+no_candidate:
return NULL;
}
static void refill_freelist(int size)
{
- struct buffer_head * bh;
+ struct buffer_head * bh, * next;
struct buffer_head * candidate[BUF_DIRTY];
- unsigned int best_time, winner;
int buffers[BUF_DIRTY];
int i;
- int needed;
+ int needed, obtained=0;
refilled = 1;
- /* If there are too many dirty buffers, we wake up the update process
- * now so as to ensure that there are still clean buffers available
- * for user processes to use (and dirty).
- */
/* We are going to try to locate this much memory. */
needed = bdf_prm.b_un.nrefill * size;
- while ((nr_free_pages > min_free_pages*2) &&
- (needed > 0) &&
- grow_buffers(GFP_BUFFER, size))
- needed -= PAGE_SIZE;
+ while ((nr_free_pages > min_free_pages*2) &&
+ grow_buffers(GFP_BUFFER, size)) {
+ obtained += PAGE_SIZE;
+ if (obtained >= needed)
+ return;
+ }
+
+ /*
+ * Update the needed amount based on the number of potentially
+ * freeable buffers. We don't want to free more than one quarter
+ * of the available buffers.
+ */
+ i = (nr_buffers_type[BUF_CLEAN] + nr_buffers_type[BUF_LOCKED]) >> 2;
+ if (i < bdf_prm.b_un.nrefill) {
+ needed = i * size;
+ if (needed < PAGE_SIZE)
+ needed = PAGE_SIZE;
+ }
+ /*
+ * OK, we cannot grow the buffer cache, now try to get some
+ * from the lru list.
+ */
repeat:
- if(needed <= 0)
+ if (obtained >= needed)
return;
- /* OK, we cannot grow the buffer cache, now try to get some
- * from the lru list.
- *
+ /*
* First set the candidate pointers to usable buffers. This
- * should be quick nearly all of the time.
+ * should be quick nearly all of the time. N.B. There must be
+ * no blocking calls after setting up the candidate[] array!
*/
-
- for(i=0; i<BUF_DIRTY; i++) {
+ for (i = BUF_CLEAN; i<BUF_DIRTY; i++) {
buffers[i] = nr_buffers_type[i];
candidate[i] = find_candidate(lru_list[i], &buffers[i], size);
}
- /* Now see which candidate wins the election. */
-
- winner = best_time = UINT_MAX;
- for(i=0; i<BUF_DIRTY; i++) {
- if(!candidate[i])
- continue;
- if(candidate[i]->b_lru_time < best_time) {
- best_time = candidate[i]->b_lru_time;
- winner = i;
- }
- }
-
- /* If we have a winner, use it, and then get a new candidate from that list. */
- if(winner != UINT_MAX) {
- i = winner;
- while (needed>0 && (bh=candidate[i])) {
- candidate[i] = bh->b_next_free;
- if(candidate[i] == bh)
- candidate[i] = NULL; /* Got last one */
- remove_from_queues(bh);
- bh->b_dev = B_FREE;
- put_last_free(bh);
- needed -= bh->b_size;
- buffers[i]--;
- if(buffers[i] == 0)
- candidate[i] = NULL;
-
- if (candidate[i] && !can_reclaim(candidate[i],size))
- candidate[i] = find_candidate(candidate[i],
- &buffers[i], size);
+ /*
+ * Select the older of the available buffers until we reach our goal.
+ */
+ for (;;) {
+ i = BUF_CLEAN;
+ if (!candidate[BUF_CLEAN]) {
+ if (!candidate[BUF_LOCKED])
+ break;
+ i = BUF_LOCKED;
}
- goto repeat;
- }
+ else if (candidate[BUF_LOCKED] &&
+ (candidate[BUF_LOCKED]->b_lru_time <
+ candidate[BUF_CLEAN ]->b_lru_time))
+ i = BUF_LOCKED;
+ /*
+ * Free the selected buffer and get the next candidate.
+ */
+ bh = candidate[i];
+ next = bh->b_next_free;
+
+ obtained += bh->b_size;
+ remove_from_queues(bh);
+ put_last_free(bh);
+ if (obtained >= needed)
+ return;
+
+ if (--buffers[i] && bh != next)
+ candidate[i] = find_candidate(next, &buffers[i], size);
+ else
+ candidate[i] = NULL;
+ }
+
+ /*
+ * If we achieved at least half of our goal, return now.
+ */
+ if (obtained >= (needed >> 1))
+ return;
/* Too bad, that was not enough. Try a little harder to grow some. */
if (nr_free_pages > min_free_pages + 5) {
if (grow_buffers(GFP_BUFFER, size)) {
- needed -= PAGE_SIZE;
+ obtained += PAGE_SIZE;
goto repeat;
}
}
-
- /* And repeat until we find something good. */
+
+ /*
+ * Make one more attempt to allocate some buffers.
+ */
if (grow_buffers(GFP_ATOMIC, size))
- needed -= PAGE_SIZE;
- else
- wakeup_bdflush(1);
+ obtained += PAGE_SIZE;
+
+ /*
+ * If we got any buffers, or another task freed some,
+ * return now to let this task proceed.
+ */
+ if (obtained || free_list[BUFSIZE_INDEX(size)]) {
+#ifdef BUFFER_DEBUG
+printk("refill_freelist: obtained %d of %d, free list=%d\n",
+obtained, needed, free_list[BUFSIZE_INDEX(size)] != NULL);
+#endif
+ return;
+ }
+
+ /*
+ * System is _very_ low on memory ... wake up bdflush and wait.
+ */
+#ifdef BUFFER_DEBUG
+printk("refill_freelist: waking bdflush\n");
+#endif
+ wakeup_bdflush(1);
+ /*
+ * While we slept, other tasks may have needed buffers and entered
+ * refill_freelist. This could be a big problem ... reset the
+ * needed amount to the absolute minimum.
+ */
+ needed = size;
goto repeat;
}
@@ -831,6 +852,8 @@
* and that it's unused (b_count=0), unlocked (buffer_locked=0), and clean.
*/
bh->b_count=1;
+ bh->b_list = BUF_CLEAN;
+ bh->b_lru_time = jiffies;
bh->b_flushtime=0;
bh->b_state=(1<<BH_Touched);
bh->b_dev=dev;
@@ -856,6 +879,16 @@
/*
+ * Put a buffer into the appropriate list, without side-effects.
+ */
+static inline void file_buffer(struct buffer_head *bh, int list)
+{
+ remove_from_queues(bh);
+ bh->b_list = list;
+ insert_into_queues(bh);
+}
+
+/*
* A buffer may need to be moved from one buffer list to another
* (e.g. in case it is not shared any more). Handle this.
*/
@@ -873,15 +906,9 @@
dispose = BUF_LOCKED;
else
dispose = BUF_CLEAN;
- if(dispose == BUF_CLEAN)
- buf->b_lru_time = jiffies;
if(dispose != buf->b_list) {
- if(dispose == BUF_DIRTY)
- buf->b_lru_time = jiffies;
- remove_from_queues(buf);
- buf->b_list = dispose;
- insert_into_queues(buf);
- if (dispose == BUF_DIRTY) {
+ file_buffer(buf, dispose);
+ if(dispose == BUF_DIRTY) {
int too_many = (nr_buffers * bdf_prm.b_un.nfract/100);
/* This buffer is dirty, maybe we need to start flushing.
--------------F57AEB0F3D8654E5E3BDEF48--