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