Thread: storage/buffer/README docs about buffer replacement are out of date
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
On Tue, Nov 10, 2015 at 3:34 AM, Andres Freund <andres@anarazel.de> wrote:
>
> 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.
>
>
> 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 think in point 5 above, it talks about the buffer returned by BufferAlloc.
Refer the point before commitid -
5d7962c6797c0baae9ffb3b5b9ac0aec7b598bc3
-5. Pin the selected buffer, release BufFreelistLock, and return the buffer.
+5. Pin the selected buffer, and return.
BufFreelistLock was released in BufferAlloc() which indicates that it talks
about pinning done in the BufferAlloc() function, so it seems we can retain
that part as it is and rest changes suggested by you seems to be fine.
Also if we see what is written around these points, I think the intention
of 5th point was to cover buffer returned by BufferAlloc().
Andres Freund wrote: > 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. I think it makes sense to keep a high-level overview in the README; in particular the description of how users of this API would use it should be there. But the implementation details should live in comments inside the file. I don't think the details of the buffer replacement algorithm should be in the README. -- Álvaro Herrera http://www.2ndQuadrant.com/ PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services