Line data    Source code

       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-2026, 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
      32            0 : datapagemap_add(datapagemap_t *map, BlockNumber blkno)
      33              : {
      34            0 :         int                     offset;
      35            0 :         int                     bitno;
      36              : 
      37            0 :         offset = blkno / 8;
      38            0 :         bitno = blkno % 8;
      39              : 
      40              :         /* enlarge or create bitmap if needed */
      41            0 :         if (map->bitmapsize <= offset)
      42              :         {
      43            0 :                 int                     oldsize = map->bitmapsize;
      44            0 :                 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            0 :                 newsize = offset + 1;
      53            0 :                 newsize += 10;
      54              : 
      55            0 :                 map->bitmap = pg_realloc(map->bitmap, newsize);
      56              : 
      57              :                 /* zero out the newly allocated region */
      58            0 :                 memset(&map->bitmap[oldsize], 0, newsize - oldsize);
      59              : 
      60            0 :                 map->bitmapsize = newsize;
      61            0 :         }
      62              : 
      63              :         /* Set the bit */
      64            0 :         map->bitmap[offset] |= (1 << bitno);
      65            0 : }
      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 *
      75            0 : datapagemap_iterate(datapagemap_t *map)
      76              : {
      77            0 :         datapagemap_iterator_t *iter;
      78              : 
      79            0 :         iter = pg_malloc(sizeof(datapagemap_iterator_t));
      80            0 :         iter->map = map;
      81            0 :         iter->nextblkno = 0;
      82              : 
      83            0 :         return iter;
      84            0 : }
      85              : 
      86              : bool
      87            0 : datapagemap_next(datapagemap_iterator_t *iter, BlockNumber *blkno)
      88              : {
      89            0 :         datapagemap_t *map = iter->map;
      90              : 
      91            0 :         for (;;)
      92              :         {
      93            0 :                 BlockNumber blk = iter->nextblkno;
      94            0 :                 int                     nextoff = blk / 8;
      95            0 :                 int                     bitno = blk % 8;
      96              : 
      97            0 :                 if (nextoff >= map->bitmapsize)
      98            0 :                         break;
      99              : 
     100            0 :                 iter->nextblkno++;
     101              : 
     102            0 :                 if (map->bitmap[nextoff] & (1 << bitno))
     103              :                 {
     104            0 :                         *blkno = blk;
     105            0 :                         return true;
     106              :                 }
     107            0 :         }
     108              : 
     109              :         /* no more set bits in this bitmap. */
     110            0 :         return false;
     111            0 : }
     112              : 
     113              : /*
     114              :  * A debugging aid. Prints out the contents of the page map.
     115              :  */
     116              : void
     117            0 : datapagemap_print(datapagemap_t *map)
     118              : {
     119            0 :         datapagemap_iterator_t *iter;
     120            0 :         BlockNumber blocknum;
     121              : 
     122            0 :         iter = datapagemap_iterate(map);
     123            0 :         while (datapagemap_next(iter, &blocknum))
     124            0 :                 pg_log_debug("block %u", blocknum);
     125              : 
     126            0 :         pg_free(iter);
     127            0 : }