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