Hi,
$subject contains:
> The "clock hand" is a buffer index, nextVictimBuffer, that moves circularly
> through all the available buffers. nextVictimBuffer is protected by the
> buffer_strategy_lock.
>
> The algorithm for a process that needs to obtain a victim buffer is:
>
> 1. Obtain buffer_strategy_lock.
>
> 2. If buffer free list is nonempty, remove its head buffer. Release
> buffer_strategy_lock. If the buffer is pinned or has a nonzero usage count,
> it cannot be used; ignore it go back to step 1. Otherwise, pin the buffer,
> and return it.
>
> 3. Otherwise, the buffer free list is empty. Select the buffer pointed to by
> nextVictimBuffer, and circularly advance nextVictimBuffer for next time.
> Release buffer_strategy_lock.
>
> 4. If the selected buffer is pinned or has a nonzero usage count, it cannot
> be used. Decrement its usage count (if nonzero), reacquire
> buffer_strategy_lock, and return to step 3 to examine the next buffer.
>
> 5. Pin the selected buffer, and return.
This is currently accurate on several levels:
a) nextVictimBuffer isn't protectec by the buffer_strategy_lock anymore.
b) The buffer free list is first checked unlocked - which 2) above doesn't document.
c) The buffer isn't actually returned pinned - instead it's kept locked.
Now a) and b) are recent oversights of mine. I'd apparently not realized
that there's detailed docs on this in buffer/README. But c) is pretty
old - essentially 5d50873 from 2005.
I wonder if it's worthwhile to go into that level of detail - seems
kinda likely to get out of date, as evidenced by it being outdated for
~10 years.
If we want to keep it, how about something like:
The "clock hand" is a buffer index, nextVictimBuffer, that moves
circularly through all the available buffers. nextVictimBuffer is
incremented atomically. The wraparound handling is protected by
buffer_strategy_lock.
The algorithm for a process that needs to obtain a victim buffer is:
1. Check, without a lock, whether the buffer free list is empty. If
so, jump to step four.
2. Obtain buffer_strategy_lock, check whether the free list is still
non-empty, and if so remove the head buffer. Release
buffer_strategy_lock. If the list is empty jump to step four.
3. If the buffer is pinned or has a nonzero usage count, it cannot be
used; go back to step 2. Otherwise, return the buffer with the header
spinlock held.
4. The buffer free list is empty. Select the buffer pointed to by
nextVictimBuffer, and circularly advance nextVictimBuffer for next time.
5. If the selected buffer is pinned or has a nonzero usage count, it
cannot be used. Decrement its usage count (if nonzero), and return to
step 4 to examine the next buffer.
6. Return the buffer with the header spinlock held.
Greetings,
Andres Freund