PostgreSQL Source Code  git master
datapagemap.c
Go to the documentation of this file.
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-2017, PostgreSQL Global Development Group
9  *
10  *-------------------------------------------------------------------------
11  */
12 
13 #include "postgres_fe.h"
14 
15 #include "datapagemap.h"
16 #include "logging.h"
17 
19 {
22 };
23 
24 /*****
25  * Public functions
26  */
27 
28 /*
29  * Add a block to the bitmap.
30  */
31 void
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  */
76 {
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
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
118 {
120  BlockNumber blocknum;
121 
122  iter = datapagemap_iterate(map);
123  while (datapagemap_next(iter, &blocknum))
124  pg_log(PG_DEBUG, " block %u\n", blocknum);
125 
126  pg_free(iter);
127 }
void datapagemap_add(datapagemap_t *map, BlockNumber blkno)
Definition: datapagemap.c:32
void * pg_malloc(size_t size)
Definition: fe_memutils.c:47
char * bitmap
Definition: datapagemap.h:18
uint32 BlockNumber
Definition: block.h:31
bool datapagemap_next(datapagemap_iterator_t *iter, BlockNumber *blkno)
Definition: datapagemap.c:87
void pg_log(eLogType type, const char *fmt,...)
Definition: logging.c:69
void * pg_realloc(void *ptr, size_t size)
Definition: fe_memutils.c:65
void datapagemap_print(datapagemap_t *map)
Definition: datapagemap.c:117
int bitmapsize
Definition: datapagemap.h:19
datapagemap_iterator_t * datapagemap_iterate(datapagemap_t *map)
Definition: datapagemap.c:75
void pg_free(void *ptr)
Definition: fe_memutils.c:105
BlockNumber nextblkno
Definition: datapagemap.c:21
datapagemap_t * map
Definition: datapagemap.c:20