1/*-------------------------------------------------------------------------
2 *
3 * datapagemap.c
4 * A data structure for keeping track of data pages that have changed.
5 *
6 * This is a fairly simple bitmap.
7 *
8 * Copyright (c) 2013-2019, PostgreSQL Global Development Group
9 *
10 *-------------------------------------------------------------------------
11 */
12
13#include "postgres_fe.h"
14
15#include "datapagemap.h"
16
17#include "common/logging.h"
18
19struct datapagemap_iterator
20{
21 datapagemap_t *map;
22 BlockNumber nextblkno;
23};
24
25/*****
26 * Public functions
27 */
28
29/*
30 * Add a block to the bitmap.
31 */
32void
33datapagemap_add(datapagemap_t *map, BlockNumber blkno)
34{
35 int offset;
36 int bitno;
37
38 offset = blkno / 8;
39 bitno = blkno % 8;
40
41 /* enlarge or create bitmap if needed */
42 if (map->bitmapsize <= offset)
43 {
44 int oldsize = map->bitmapsize;
45 int newsize;
46
47 /*
48 * The minimum to hold the new bit is offset + 1. But add some
49 * headroom, so that we don't need to repeatedly enlarge the bitmap in
50 * the common case that blocks are modified in order, from beginning
51 * of a relation to the end.
52 */
53 newsize = offset + 1;
54 newsize += 10;
55
56 map->bitmap = pg_realloc(map->bitmap, newsize);
57
58 /* zero out the newly allocated region */
59 memset(&map->bitmap[oldsize], 0, newsize - oldsize);
60
61 map->bitmapsize = newsize;
62 }
63
64 /* Set the bit */
65 map->bitmap[offset] |= (1 << bitno);
66}
67
68/*
69 * Start iterating through all entries in the page map.
70 *
71 * After datapagemap_iterate, call datapagemap_next to return the entries,
72 * until it returns false. After you're done, use pg_free() to destroy the
73 * iterator.
74 */
75datapagemap_iterator_t *
76datapagemap_iterate(datapagemap_t *map)
77{
78 datapagemap_iterator_t *iter;
79
80 iter = pg_malloc(sizeof(datapagemap_iterator_t));
81 iter->map = map;
82 iter->nextblkno = 0;
83
84 return iter;
85}
86
87bool
88datapagemap_next(datapagemap_iterator_t *iter, BlockNumber *blkno)
89{
90 datapagemap_t *map = iter->map;
91
92 for (;;)
93 {
94 BlockNumber blk = iter->nextblkno;
95 int nextoff = blk / 8;
96 int bitno = blk % 8;
97
98 if (nextoff >= map->bitmapsize)
99 break;
100
101 iter->nextblkno++;
102
103 if (map->bitmap[nextoff] & (1 << bitno))
104 {
105 *blkno = blk;
106 return true;
107 }
108 }
109
110 /* no more set bits in this bitmap. */
111 return false;
112}
113
114/*
115 * A debugging aid. Prints out the contents of the page map.
116 */
117void
118datapagemap_print(datapagemap_t *map)
119{
120 datapagemap_iterator_t *iter;
121 BlockNumber blocknum;
122
123 iter = datapagemap_iterate(map);
124 while (datapagemap_next(iter, &blocknum))
125 pg_log_debug("block %u", blocknum);
126
127 pg_free(iter);
128}
129