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