← Back to branch summary

~ubuntu-branches/ubuntu/oneiric/postgresql-9.1/oneiric-security

« back to all changes in this revision

Viewing changes to src/backend/storage/buffer/freelist.c

  • Committer: Bazaar Package Importer
  • Author(s): Martin Pitt
  • Date: 2011-05-11 10:41:53 UTC
  • Revision ID: james.westby@ubuntu.com-20110511104153-psbh2o58553fv1m0
Tags: upstream-9.1~beta1
Import upstream version 9.1~beta1

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/backend/storage/buffer/freelist.c
 
1
/*-------------------------------------------------------------------------
 
2
 *
 
3
 * freelist.c
 
4
 *        routines for managing the buffer pool's replacement strategy.
 
5
 *
 
6
 *
 
7
 * Portions Copyright (c) 1996-2011, PostgreSQL Global Development Group
 
8
 * Portions Copyright (c) 1994, Regents of the University of California
 
9
 *
 
10
 *
 
11
 * IDENTIFICATION
 
12
 *        src/backend/storage/buffer/freelist.c
 
13
 *
 
14
 *-------------------------------------------------------------------------
 
15
 */
 
16
#include "postgres.h"
 
17
 
 
18
#include "storage/buf_internals.h"
 
19
#include "storage/bufmgr.h"
 
20
 
 
21
 
 
22
/*
 
23
 * The shared freelist control information.
 
24
 */
 
25
typedef struct
 
26
{
 
27
        /* Clock sweep hand: index of next buffer to consider grabbing */
 
28
        int                     nextVictimBuffer;
 
29
 
 
30
        int                     firstFreeBuffer;        /* Head of list of unused buffers */
 
31
        int                     lastFreeBuffer; /* Tail of list of unused buffers */
 
32
 
 
33
        /*
 
34
         * NOTE: lastFreeBuffer is undefined when firstFreeBuffer is -1 (that is,
 
35
         * when the list is empty)
 
36
         */
 
37
 
 
38
        /*
 
39
         * Statistics.  These counters should be wide enough that they can't
 
40
         * overflow during a single bgwriter cycle.
 
41
         */
 
42
        uint32          completePasses; /* Complete cycles of the clock sweep */
 
43
        uint32          numBufferAllocs;        /* Buffers allocated since last reset */
 
44
} BufferStrategyControl;
 
45
 
 
46
/* Pointers to shared state */
 
47
static BufferStrategyControl *StrategyControl = NULL;
 
48
 
 
49
/*
 
50
 * Private (non-shared) state for managing a ring of shared buffers to re-use.
 
51
 * This is currently the only kind of BufferAccessStrategy object, but someday
 
52
 * we might have more kinds.
 
53
 */
 
54
typedef struct BufferAccessStrategyData
 
55
{
 
56
        /* Overall strategy type */
 
57
        BufferAccessStrategyType btype;
 
58
        /* Number of elements in buffers[] array */
 
59
        int                     ring_size;
 
60
 
 
61
        /*
 
62
         * Index of the "current" slot in the ring, ie, the one most recently
 
63
         * returned by GetBufferFromRing.
 
64
         */
 
65
        int                     current;
 
66
 
 
67
        /*
 
68
         * True if the buffer just returned by StrategyGetBuffer had been in the
 
69
         * ring already.
 
70
         */
 
71
        bool            current_was_in_ring;
 
72
 
 
73
        /*
 
74
         * Array of buffer numbers.  InvalidBuffer (that is, zero) indicates we
 
75
         * have not yet selected a buffer for this ring slot.  For allocation
 
76
         * simplicity this is palloc'd together with the fixed fields of the
 
77
         * struct.
 
78
         */
 
79
        Buffer          buffers[1];             /* VARIABLE SIZE ARRAY */
 
80
}       BufferAccessStrategyData;
 
81
 
 
82
 
 
83
/* Prototypes for internal functions */
 
84
static volatile BufferDesc *GetBufferFromRing(BufferAccessStrategy strategy);
 
85
static void AddBufferToRing(BufferAccessStrategy strategy,
 
86
                                volatile BufferDesc *buf);
 
87
 
 
88
 
 
89
/*
 
90
 * StrategyGetBuffer
 
91
 *
 
92
 *      Called by the bufmgr to get the next candidate buffer to use in
 
93
 *      BufferAlloc(). The only hard requirement BufferAlloc() has is that
 
94
 *      the selected buffer must not currently be pinned by anyone.
 
95
 *
 
96
 *      strategy is a BufferAccessStrategy object, or NULL for default strategy.
 
97
 *
 
98
 *      To ensure that no one else can pin the buffer before we do, we must
 
99
 *      return the buffer with the buffer header spinlock still held.  If
 
100
 *      *lock_held is set on exit, we have returned with the BufFreelistLock
 
101
 *      still held, as well; the caller must release that lock once the spinlock
 
102
 *      is dropped.  We do it that way because releasing the BufFreelistLock
 
103
 *      might awaken other processes, and it would be bad to do the associated
 
104
 *      kernel calls while holding the buffer header spinlock.
 
105
 */
 
106
volatile BufferDesc *
 
107
StrategyGetBuffer(BufferAccessStrategy strategy, bool *lock_held)
 
108
{
 
109
        volatile BufferDesc *buf;
 
110
        int                     trycounter;
 
111
 
 
112
        /*
 
113
         * If given a strategy object, see whether it can select a buffer. We
 
114
         * assume strategy objects don't need the BufFreelistLock.
 
115
         */
 
116
        if (strategy != NULL)
 
117
        {
 
118
                buf = GetBufferFromRing(strategy);
 
119
                if (buf != NULL)
 
120
                {
 
121
                        *lock_held = false;
 
122
                        return buf;
 
123
                }
 
124
        }
 
125
 
 
126
        /* Nope, so lock the freelist */
 
127
        *lock_held = true;
 
128
        LWLockAcquire(BufFreelistLock, LW_EXCLUSIVE);
 
129
 
 
130
        /*
 
131
         * We count buffer allocation requests so that the bgwriter can estimate
 
132
         * the rate of buffer consumption.      Note that buffers recycled by a
 
133
         * strategy object are intentionally not counted here.
 
134
         */
 
135
        StrategyControl->numBufferAllocs++;
 
136
 
 
137
        /*
 
138
         * Try to get a buffer from the freelist.  Note that the freeNext fields
 
139
         * are considered to be protected by the BufFreelistLock not the
 
140
         * individual buffer spinlocks, so it's OK to manipulate them without
 
141
         * holding the spinlock.
 
142
         */
 
143
        while (StrategyControl->firstFreeBuffer >= 0)
 
144
        {
 
145
                buf = &BufferDescriptors[StrategyControl->firstFreeBuffer];
 
146
                Assert(buf->freeNext != FREENEXT_NOT_IN_LIST);
 
147
 
 
148
                /* Unconditionally remove buffer from freelist */
 
149
                StrategyControl->firstFreeBuffer = buf->freeNext;
 
150
                buf->freeNext = FREENEXT_NOT_IN_LIST;
 
151
 
 
152
                /*
 
153
                 * If the buffer is pinned or has a nonzero usage_count, we cannot use
 
154
                 * it; discard it and retry.  (This can only happen if VACUUM put a
 
155
                 * valid buffer in the freelist and then someone else used it before
 
156
                 * we got to it.  It's probably impossible altogether as of 8.3, but
 
157
                 * we'd better check anyway.)
 
158
                 */
 
159
                LockBufHdr(buf);
 
160
                if (buf->refcount == 0 && buf->usage_count == 0)
 
161
                {
 
162
                        if (strategy != NULL)
 
163
                                AddBufferToRing(strategy, buf);
 
164
                        return buf;
 
165
                }
 
166
                UnlockBufHdr(buf);
 
167
        }
 
168
 
 
169
        /* Nothing on the freelist, so run the "clock sweep" algorithm */
 
170
        trycounter = NBuffers;
 
171
        for (;;)
 
172
        {
 
173
                buf = &BufferDescriptors[StrategyControl->nextVictimBuffer];
 
174
 
 
175
                if (++StrategyControl->nextVictimBuffer >= NBuffers)
 
176
                {
 
177
                        StrategyControl->nextVictimBuffer = 0;
 
178
                        StrategyControl->completePasses++;
 
179
                }
 
180
 
 
181
                /*
 
182
                 * If the buffer is pinned or has a nonzero usage_count, we cannot use
 
183
                 * it; decrement the usage_count (unless pinned) and keep scanning.
 
184
                 */
 
185
                LockBufHdr(buf);
 
186
                if (buf->refcount == 0)
 
187
                {
 
188
                        if (buf->usage_count > 0)
 
189
                        {
 
190
                                buf->usage_count--;
 
191
                                trycounter = NBuffers;
 
192
                        }
 
193
                        else
 
194
                        {
 
195
                                /* Found a usable buffer */
 
196
                                if (strategy != NULL)
 
197
                                        AddBufferToRing(strategy, buf);
 
198
                                return buf;
 
199
                        }
 
200
                }
 
201
                else if (--trycounter == 0)
 
202
                {
 
203
                        /*
 
204
                         * We've scanned all the buffers without making any state changes,
 
205
                         * so all the buffers are pinned (or were when we looked at them).
 
206
                         * We could hope that someone will free one eventually, but it's
 
207
                         * probably better to fail than to risk getting stuck in an
 
208
                         * infinite loop.
 
209
                         */
 
210
                        UnlockBufHdr(buf);
 
211
                        elog(ERROR, "no unpinned buffers available");
 
212
                }
 
213
                UnlockBufHdr(buf);
 
214
        }
 
215
 
 
216
        /* not reached */
 
217
        return NULL;
 
218
}
 
219
 
 
220
/*
 
221
 * StrategyFreeBuffer: put a buffer on the freelist
 
222
 */
 
223
void
 
224
StrategyFreeBuffer(volatile BufferDesc *buf)
 
225
{
 
226
        LWLockAcquire(BufFreelistLock, LW_EXCLUSIVE);
 
227
 
 
228
        /*
 
229
         * It is possible that we are told to put something in the freelist that
 
230
         * is already in it; don't screw up the list if so.
 
231
         */
 
232
        if (buf->freeNext == FREENEXT_NOT_IN_LIST)
 
233
        {
 
234
                buf->freeNext = StrategyControl->firstFreeBuffer;
 
235
                if (buf->freeNext < 0)
 
236
                        StrategyControl->lastFreeBuffer = buf->buf_id;
 
237
                StrategyControl->firstFreeBuffer = buf->buf_id;
 
238
        }
 
239
 
 
240
        LWLockRelease(BufFreelistLock);
 
241
}
 
242
 
 
243
/*
 
244
 * StrategySyncStart -- tell BufferSync where to start syncing
 
245
 *
 
246
 * The result is the buffer index of the best buffer to sync first.
 
247
 * BufferSync() will proceed circularly around the buffer array from there.
 
248
 *
 
249
 * In addition, we return the completed-pass count (which is effectively
 
250
 * the higher-order bits of nextVictimBuffer) and the count of recent buffer
 
251
 * allocs if non-NULL pointers are passed.      The alloc count is reset after
 
252
 * being read.
 
253
 */
 
254
int
 
255
StrategySyncStart(uint32 *complete_passes, uint32 *num_buf_alloc)
 
256
{
 
257
        int                     result;
 
258
 
 
259
        LWLockAcquire(BufFreelistLock, LW_EXCLUSIVE);
 
260
        result = StrategyControl->nextVictimBuffer;
 
261
        if (complete_passes)
 
262
                *complete_passes = StrategyControl->completePasses;
 
263
        if (num_buf_alloc)
 
264
        {
 
265
                *num_buf_alloc = StrategyControl->numBufferAllocs;
 
266
                StrategyControl->numBufferAllocs = 0;
 
267
        }
 
268
        LWLockRelease(BufFreelistLock);
 
269
        return result;
 
270
}
 
271
 
 
272
 
 
273
/*
 
274
 * StrategyShmemSize
 
275
 *
 
276
 * estimate the size of shared memory used by the freelist-related structures.
 
277
 *
 
278
 * Note: for somewhat historical reasons, the buffer lookup hashtable size
 
279
 * is also determined here.
 
280
 */
 
281
Size
 
282
StrategyShmemSize(void)
 
283
{
 
284
        Size            size = 0;
 
285
 
 
286
        /* size of lookup hash table ... see comment in StrategyInitialize */
 
287
        size = add_size(size, BufTableShmemSize(NBuffers + NUM_BUFFER_PARTITIONS));
 
288
 
 
289
        /* size of the shared replacement strategy control block */
 
290
        size = add_size(size, MAXALIGN(sizeof(BufferStrategyControl)));
 
291
 
 
292
        return size;
 
293
}
 
294
 
 
295
/*
 
296
 * StrategyInitialize -- initialize the buffer cache replacement
 
297
 *              strategy.
 
298
 *
 
299
 * Assumes: All of the buffers are already built into a linked list.
 
300
 *              Only called by postmaster and only during initialization.
 
301
 */
 
302
void
 
303
StrategyInitialize(bool init)
 
304
{
 
305
        bool            found;
 
306
 
 
307
        /*
 
308
         * Initialize the shared buffer lookup hashtable.
 
309
         *
 
310
         * Since we can't tolerate running out of lookup table entries, we must be
 
311
         * sure to specify an adequate table size here.  The maximum steady-state
 
312
         * usage is of course NBuffers entries, but BufferAlloc() tries to insert
 
313
         * a new entry before deleting the old.  In principle this could be
 
314
         * happening in each partition concurrently, so we could need as many as
 
315
         * NBuffers + NUM_BUFFER_PARTITIONS entries.
 
316
         */
 
317
        InitBufTable(NBuffers + NUM_BUFFER_PARTITIONS);
 
318
 
 
319
        /*
 
320
         * Get or create the shared strategy control block
 
321
         */
 
322
        StrategyControl = (BufferStrategyControl *)
 
323
                ShmemInitStruct("Buffer Strategy Status",
 
324
                                                sizeof(BufferStrategyControl),
 
325
                                                &found);
 
326
 
 
327
        if (!found)
 
328
        {
 
329
                /*
 
330
                 * Only done once, usually in postmaster
 
331
                 */
 
332
                Assert(init);
 
333
 
 
334
                /*
 
335
                 * Grab the whole linked list of free buffers for our strategy. We
 
336
                 * assume it was previously set up by InitBufferPool().
 
337
                 */
 
338
                StrategyControl->firstFreeBuffer = 0;
 
339
                StrategyControl->lastFreeBuffer = NBuffers - 1;
 
340
 
 
341
                /* Initialize the clock sweep pointer */
 
342
                StrategyControl->nextVictimBuffer = 0;
 
343
 
 
344
                /* Clear statistics */
 
345
                StrategyControl->completePasses = 0;
 
346
                StrategyControl->numBufferAllocs = 0;
 
347
        }
 
348
        else
 
349
                Assert(!init);
 
350
}
 
351
 
 
352
 
 
353
/* ----------------------------------------------------------------
 
354
 *                              Backend-private buffer ring management
 
355
 * ----------------------------------------------------------------
 
356
 */
 
357
 
 
358
 
 
359
/*
 
360
 * GetAccessStrategy -- create a BufferAccessStrategy object
 
361
 *
 
362
 * The object is allocated in the current memory context.
 
363
 */
 
364
BufferAccessStrategy
 
365
GetAccessStrategy(BufferAccessStrategyType btype)
 
366
{
 
367
        BufferAccessStrategy strategy;
 
368
        int                     ring_size;
 
369
 
 
370
        /*
 
371
         * Select ring size to use.  See buffer/README for rationales.
 
372
         *
 
373
         * Note: if you change the ring size for BAS_BULKREAD, see also
 
374
         * SYNC_SCAN_REPORT_INTERVAL in access/heap/syncscan.c.
 
375
         */
 
376
        switch (btype)
 
377
        {
 
378
                case BAS_NORMAL:
 
379
                        /* if someone asks for NORMAL, just give 'em a "default" object */
 
380
                        return NULL;
 
381
 
 
382
                case BAS_BULKREAD:
 
383
                        ring_size = 256 * 1024 / BLCKSZ;
 
384
                        break;
 
385
                case BAS_BULKWRITE:
 
386
                        ring_size = 16 * 1024 * 1024 / BLCKSZ;
 
387
                        break;
 
388
                case BAS_VACUUM:
 
389
                        ring_size = 256 * 1024 / BLCKSZ;
 
390
                        break;
 
391
 
 
392
                default:
 
393
                        elog(ERROR, "unrecognized buffer access strategy: %d",
 
394
                                 (int) btype);
 
395
                        return NULL;            /* keep compiler quiet */
 
396
        }
 
397
 
 
398
        /* Make sure ring isn't an undue fraction of shared buffers */
 
399
        ring_size = Min(NBuffers / 8, ring_size);
 
400
 
 
401
        /* Allocate the object and initialize all elements to zeroes */
 
402
        strategy = (BufferAccessStrategy)
 
403
                palloc0(offsetof(BufferAccessStrategyData, buffers) +
 
404
                                ring_size * sizeof(Buffer));
 
405
 
 
406
        /* Set fields that don't start out zero */
 
407
        strategy->btype = btype;
 
408
        strategy->ring_size = ring_size;
 
409
 
 
410
        return strategy;
 
411
}
 
412
 
 
413
/*
 
414
 * FreeAccessStrategy -- release a BufferAccessStrategy object
 
415
 *
 
416
 * A simple pfree would do at the moment, but we would prefer that callers
 
417
 * don't assume that much about the representation of BufferAccessStrategy.
 
418
 */
 
419
void
 
420
FreeAccessStrategy(BufferAccessStrategy strategy)
 
421
{
 
422
        /* don't crash if called on a "default" strategy */
 
423
        if (strategy != NULL)
 
424
                pfree(strategy);
 
425
}
 
426
 
 
427
/*
 
428
 * GetBufferFromRing -- returns a buffer from the ring, or NULL if the
 
429
 *              ring is empty.
 
430
 *
 
431
 * The bufhdr spin lock is held on the returned buffer.
 
432
 */
 
433
static volatile BufferDesc *
 
434
GetBufferFromRing(BufferAccessStrategy strategy)
 
435
{
 
436
        volatile BufferDesc *buf;
 
437
        Buffer          bufnum;
 
438
 
 
439
        /* Advance to next ring slot */
 
440
        if (++strategy->current >= strategy->ring_size)
 
441
                strategy->current = 0;
 
442
 
 
443
        /*
 
444
         * If the slot hasn't been filled yet, tell the caller to allocate a new
 
445
         * buffer with the normal allocation strategy.  He will then fill this
 
446
         * slot by calling AddBufferToRing with the new buffer.
 
447
         */
 
448
        bufnum = strategy->buffers[strategy->current];
 
449
        if (bufnum == InvalidBuffer)
 
450
        {
 
451
                strategy->current_was_in_ring = false;
 
452
                return NULL;
 
453
        }
 
454
 
 
455
        /*
 
456
         * If the buffer is pinned we cannot use it under any circumstances.
 
457
         *
 
458
         * If usage_count is 0 or 1 then the buffer is fair game (we expect 1,
 
459
         * since our own previous usage of the ring element would have left it
 
460
         * there, but it might've been decremented by clock sweep since then). A
 
461
         * higher usage_count indicates someone else has touched the buffer, so we
 
462
         * shouldn't re-use it.
 
463
         */
 
464
        buf = &BufferDescriptors[bufnum - 1];
 
465
        LockBufHdr(buf);
 
466
        if (buf->refcount == 0 && buf->usage_count <= 1)
 
467
        {
 
468
                strategy->current_was_in_ring = true;
 
469
                return buf;
 
470
        }
 
471
        UnlockBufHdr(buf);
 
472
 
 
473
        /*
 
474
         * Tell caller to allocate a new buffer with the normal allocation
 
475
         * strategy.  He'll then replace this ring element via AddBufferToRing.
 
476
         */
 
477
        strategy->current_was_in_ring = false;
 
478
        return NULL;
 
479
}
 
480
 
 
481
/*
 
482
 * AddBufferToRing -- add a buffer to the buffer ring
 
483
 *
 
484
 * Caller must hold the buffer header spinlock on the buffer.  Since this
 
485
 * is called with the spinlock held, it had better be quite cheap.
 
486
 */
 
487
static void
 
488
AddBufferToRing(BufferAccessStrategy strategy, volatile BufferDesc *buf)
 
489
{
 
490
        strategy->buffers[strategy->current] = BufferDescriptorGetBuffer(buf);
 
491
}
 
492
 
 
493
/*
 
494
 * StrategyRejectBuffer -- consider rejecting a dirty buffer
 
495
 *
 
496
 * When a nondefault strategy is used, the buffer manager calls this function
 
497
 * when it turns out that the buffer selected by StrategyGetBuffer needs to
 
498
 * be written out and doing so would require flushing WAL too.  This gives us
 
499
 * a chance to choose a different victim.
 
500
 *
 
501
 * Returns true if buffer manager should ask for a new victim, and false
 
502
 * if this buffer should be written and re-used.
 
503
 */
 
504
bool
 
505
StrategyRejectBuffer(BufferAccessStrategy strategy, volatile BufferDesc *buf)
 
506
{
 
507
        /* We only do this in bulkread mode */
 
508
        if (strategy->btype != BAS_BULKREAD)
 
509
                return false;
 
510
 
 
511
        /* Don't muck with behavior of normal buffer-replacement strategy */
 
512
        if (!strategy->current_was_in_ring ||
 
513
          strategy->buffers[strategy->current] != BufferDescriptorGetBuffer(buf))
 
514
                return false;
 
515
 
 
516
        /*
 
517
         * Remove the dirty buffer from the ring; necessary to prevent infinite
 
518
         * loop if all ring members are dirty.
 
519
         */
 
520
        strategy->buffers[strategy->current] = InvalidBuffer;
 
521
 
 
522
        return true;
 
523
}