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