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