src/libcaptive/fs/mcb.c

   1 /* $Id$
   2  * reactos MCB (map control block) functions emulation of libcaptive
   3  * Copyright (C) 2003 Jan Kratochvil <project-captive@jankratochvil.net>
   4  *
   5  * This program is free software; you can redistribute it and/or modify
   6  * it under the terms of the GNU General Public License as published by
   7  * the Free Software Foundation; exactly version 2 of June 1991 is required
   8  *
   9  * This program is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12  * GNU General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU General Public License
  15  * along with this program; if not, write to the Free Software
  16  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  17  */
  18
  19
  20 #include "config.h"
  21
  22 #include "reactos/ddk/fsfuncs.h"        /* self */
  23 #include <glib/gmessages.h>
  24 #include "reactos/ntos/types.h" /* for VOID */
  25 #include <glib/gtree.h>
  26 #include <glib/ghash.h>
  27 #include "reactos/ddk/exfuncs.h"        /* for ExInitializeFastMutex() */
  28 #include "captive/macros.h"
  29
  30
  31 /* We use only real 'mapping' runs; we do not store 'holes' to our GTree.
  32  * Our first 'struct run' has RunIndex #0, the next 'struct run' RunIndex #2 etc.
  33  * The odd RunIndex values are computed from the neighbour 'struct run's.
  34  */
  35 struct run {
  36         LONGLONG Vbn_start;
  37         LONGLONG Vbn_end;       /* Vbn_start+SectorCount; that means +1 after the last sector */
  38         LONGLONG Lbn_start;     /* Lbn of 'Vbn_start' */
  39         };
  40
  41 struct Mcb_priv {
  42         GTree *gtree;   /* map (struct run *)->(struct run *) */
  43         };
  44
  45 static const struct run *run_compare_func_last_a_run;
  46 static const struct run *run_compare_func_last_b_run;
  47 static const struct run *run_compare_func_minus_a_run;  /* last run where we returned -1 */
  48 static const struct run *run_compare_func_minus_b_run;
  49 static const struct run *run_compare_func_plus_a_run;   /* last run where we returned +1 */
  50 static const struct run *run_compare_func_plus_b_run;
  51
  52 static gint run_compare_func(const struct run *a_run,const struct run *b_run,gpointer user_data /* unused */)
  53 {
  54 gint r;
  55
  56         g_return_val_if_fail(a_run!=NULL,0);
  57         g_return_val_if_fail(a_run->Vbn_end>a_run->Vbn_start,0);
  58         g_return_val_if_fail(b_run!=NULL,0);
  59         g_return_val_if_fail(b_run->Vbn_end>b_run->Vbn_start,0);
  60
  61         run_compare_func_last_a_run=a_run;
  62         run_compare_func_last_b_run=b_run;
  63
  64         if (1
  65                         && !(r=(a_run->Vbn_start>b_run->Vbn_start)-(a_run->Vbn_start<b_run->Vbn_start))
  66                         && !(r=(a_run->Vbn_end  >b_run->Vbn_end  )-(a_run->Vbn_end  <b_run->Vbn_end  )))
  67                 r=0;
  68
  69         if (r<0) {
  70                 run_compare_func_minus_a_run=a_run;
  71                 run_compare_func_minus_b_run=b_run;
  72                 }
  73         else if (r>0) {
  74                 run_compare_func_plus_a_run=a_run;
  75                 run_compare_func_plus_b_run=b_run;
  76                 }
  77
  78         return r;
  79 }
  80
  81 static void run_destroy_func(struct run *run)
  82 {
  83         g_return_if_fail(run!=NULL);
  84
  85         g_free(run);
  86 }
  87
  88 /* map (LARGE_MCB *)->(struct Mcb_priv *) */
  89 static GHashTable *Mcb_hash;
  90
  91 static void Mcb_hash_init(void)
  92 {
  93         if (Mcb_hash)
  94                 return;
  95         Mcb_hash=g_hash_table_new(
  96                         g_direct_hash,  /* key_compare_func */
  97                         g_direct_equal);        /* key_compare_data */
  98 }
  99
 100
 101 /**
 102  * FsRtlInitializeLargeMcb:
 103  * @Mcb: Allocated memory to be initialized as #PLARGE_MCB.
 104  * %NULL value is forbidden.
 105  * @PoolType: Memory type to use for the items. Ignored by libcaptive.
 106  *
 107  * You must use this function to be able to pass @Mcb to any other
 108  * FsRtl*LargeMcb*() function.
 109  */
 110 VOID FsRtlInitializeLargeMcb(IN PLARGE_MCB Mcb,IN POOL_TYPE PoolType)
 111 {
 112 struct Mcb_priv *Mcb_priv;
 113
 114         g_return_if_fail(Mcb!=NULL);
 115
 116         Mcb_hash_init();
 117         g_return_if_fail(NULL==g_hash_table_lookup(Mcb_hash,Mcb));
 118
 119         ExInitializeFastMutex(&Mcb->FastMutex);
 120         Mcb->MaximumPairCount=0;
 121         Mcb->PairCount=0;
 122         Mcb->PoolType=PoolType;
 123         Mcb->Mapping=NULL;
 124
 125         captive_new(Mcb_priv);
 126         Mcb_priv->gtree=g_tree_new_full(
 127                         (GCompareDataFunc)run_compare_func,     /* key_compare_func */
 128                         NULL,   /* key_compare_data */
 129                         (GDestroyNotify)run_destroy_func,       /* key_destroy_func */
 130                         NULL);  /* value_destroy_func */
 131
 132         g_hash_table_insert(Mcb_hash,
 133                         Mcb,    /* key */
 134                         Mcb_priv);      /* value */
 135 }
 136
 137
 138 /**
 139  * FsRtlUninitializeLargeMcb:
 140  * @Mcb: #PLARGE_MCB initialized by FsRtlInitializeLargeMcb().
 141  * %NULL value is forbidden.
 142  *
 143  * Frees all the resources associated with @Mcb.
 144  * You must not pass this pointer to any FsRtl*LargeMcb*() function afterwards.
 145  */
 146 VOID FsRtlUninitializeLargeMcb(IN PLARGE_MCB Mcb)
 147 {
 148 struct Mcb_priv *Mcb_priv;
 149 gboolean errbool;
 150
 151         g_return_if_fail(Mcb!=NULL);
 152
 153         Mcb_hash_init();
 154         Mcb_priv=g_hash_table_lookup(Mcb_hash,Mcb);
 155         g_return_if_fail(Mcb_priv!=NULL);
 156
 157         errbool=g_hash_table_remove(Mcb_hash,Mcb);
 158         g_assert(errbool==TRUE);
 159         g_tree_destroy(Mcb_priv->gtree);
 160         g_free(Mcb_priv);
 161 }
 162
 163
 164 static gint run_intersect_compare_func(const struct run *haystack_run,const struct run *needle_run)
 165 {
 166 gint r;
 167 struct run common_run;
 168
 169         g_return_val_if_fail(haystack_run!=NULL,0);
 170         g_return_val_if_fail(haystack_run->Vbn_end>haystack_run->Vbn_start,0);
 171         g_return_val_if_fail(needle_run!=NULL,0);
 172         g_return_val_if_fail(needle_run->Vbn_end>needle_run->Vbn_start,0);
 173
 174         common_run.Vbn_start=MAX(haystack_run->Vbn_start,needle_run->Vbn_start);
 175         common_run.Vbn_end  =MIN(haystack_run->Vbn_end  ,needle_run->Vbn_end  );
 176
 177         if (common_run.Vbn_end>common_run.Vbn_start)
 178                 return 0;
 179         r=run_compare_func(needle_run,haystack_run,
 180                         NULL);  /* user_data; unused */
 181         g_assert(r!=0); /* otherwise we would hit it by 'common_run' */
 182         return r;
 183 }
 184
 185
 186 /**
 187  * FsRtlRemoveLargeMcbEntry:
 188  * @Mcb: #PLARGE_MCB initialized by FsRtlInitializeLargeMcb().
 189  * %NULL value is forbidden.
 190  * @Vbn: Starting virtual block number to specify the range to delete.
 191  * @SectorCount: Length of the range to delete.
 192  * Value less or equal to %0 is forbidden; FIXME: Is it W32 compliant?
 193  *
 194  * Deletes any possible @Mcb mappings in the given range @Vbn ... @Vbn+@SectorCount-1.
 195  * This call has no problems if no mappings exist there yet.
 196  */
 197 VOID FsRtlRemoveLargeMcbEntry(IN PLARGE_MCB Mcb,IN LONGLONG Vbn,IN LONGLONG SectorCount)
 198 {
 199 struct Mcb_priv *Mcb_priv;
 200 struct run needle_run,*haystack_run;
 201
 202         g_return_if_fail(Mcb!=NULL);
 203         g_return_if_fail(SectorCount>0);
 204         g_return_if_fail(Vbn+SectorCount>Vbn);
 205         /* FIXME: We are unable to delete the absolutely last sector G_MAXINT64 by this implementation! */
 206         g_return_if_fail(Vbn+SectorCount+1>Vbn);
 207
 208         Mcb_hash_init();
 209         Mcb_priv=g_hash_table_lookup(Mcb_hash,Mcb);
 210         g_return_if_fail(Mcb_priv!=NULL);
 211
 212         needle_run.Vbn_start=Vbn;
 213         needle_run.Vbn_end=Vbn+SectorCount;
 214
 215         /* adjust/destroy all intersecting ranges */
 216         while ((haystack_run=g_tree_search(Mcb_priv->gtree,(GCompareFunc)run_intersect_compare_func,&needle_run))) {
 217                 /**/ if (haystack_run->Vbn_start<needle_run.Vbn_start) {
 218                         g_assert(haystack_run->Vbn_end  >needle_run.Vbn_start);
 219                         haystack_run->Vbn_end  =needle_run.Vbn_start;
 220                         }
 221                 else if (haystack_run->Vbn_end  >needle_run.Vbn_end  ) {
 222                         g_assert(haystack_run->Vbn_start<needle_run.Vbn_end  );
 223                         haystack_run->Vbn_start=needle_run.Vbn_end;
 224                         }
 225                 else {
 226                         g_assert(needle_run.Vbn_start>=haystack_run->Vbn_start);
 227                         g_assert(needle_run.Vbn_end  <=haystack_run->Vbn_end  );
 228                         g_tree_remove(Mcb_priv->gtree,haystack_run);
 229                         }
 230                 }
 231 }
 232
 233
 234 /**
 235  * FsRtlAddLargeMcbEntry:
 236  * @Mcb: #PLARGE_MCB initialized by FsRtlInitializeLargeMcb().
 237  * %NULL value is forbidden.
 238  * @Vbn: Starting virtual block number of the wished range.
 239  * @Lbn: Starting logical block number of the wished range.
 240  * @SectorCount: Length of the wished range.
 241  * Value less or equal to %0 is forbidden; FIXME: Is it W32 compliant?
 242  *
 243  * Adds the specified range @Vbn ... @Vbn+@SectorCount-1 to @Mcb.
 244  * Any mappings previously in this range are deleted first.
 245  *
 246  * Returns: %TRUE if successful.
 247  */
 248 BOOLEAN FsRtlAddLargeMcbEntry(IN PLARGE_MCB Mcb,IN LONGLONG Vbn,IN LONGLONG Lbn,IN LONGLONG SectorCount)
 249 {
 250 struct Mcb_priv *Mcb_priv;
 251 struct run *insert_run,current_run,needle_run,*lower_run,*higher_run;
 252
 253         g_return_val_if_fail(Mcb!=NULL,FALSE);
 254         g_return_val_if_fail(SectorCount>0,FALSE);
 255
 256         Mcb_hash_init();
 257         Mcb_priv=g_hash_table_lookup(Mcb_hash,Mcb);
 258         g_return_val_if_fail(Mcb_priv!=NULL,FALSE);
 259
 260         /* clean any possible previous entries in our range */
 261         FsRtlRemoveLargeMcbEntry(Mcb,Vbn,SectorCount);
 262
 263         /* initially we think we will be inserted as a separate run */
 264         current_run.Vbn_start=Vbn;
 265         current_run.Vbn_end  =Vbn+SectorCount;
 266         current_run.Lbn_start=Lbn;
 267
 268         /* optionally merge with lower run */
 269         needle_run.Vbn_start=current_run.Vbn_start-1;
 270         needle_run.Vbn_end  =needle_run.Vbn_start+1;
 271         if ((lower_run=g_tree_search(Mcb_priv->gtree,(GCompareFunc)run_intersect_compare_func,&needle_run))) {
 272                 g_assert(lower_run->Vbn_end==current_run.Vbn_start);
 273                 current_run.Vbn_start=lower_run->Vbn_start;
 274                 g_tree_remove(Mcb_priv->gtree,lower_run);
 275                 }
 276
 277         /* optionally merge with higher run */
 278         needle_run.Vbn_start=current_run.Vbn_end;
 279         needle_run.Vbn_end  =needle_run.Vbn_start+1;
 280         if ((higher_run=g_tree_search(Mcb_priv->gtree,(GCompareFunc)run_intersect_compare_func,&needle_run))) {
 281                 g_assert(higher_run->Vbn_start==current_run.Vbn_end);
 282                 current_run.Vbn_end=higher_run->Vbn_end;
 283                 g_tree_remove(Mcb_priv->gtree,higher_run);
 284                 }
 285
 286         /* finally insert the resulting run */
 287         captive_new(insert_run);
 288         *insert_run=current_run;
 289         g_tree_insert(Mcb_priv->gtree,insert_run,insert_run);
 290
 291         return TRUE;    /* success */
 292 }
 293
 294
 295 struct FsRtlGetNextLargeMcbEntry_input {
 296         ULONG RunIndex_remaining;
 297         struct run *run_found;
 298         struct run *run_found_lower,*run_found_higher;
 299         };
 300
 301 static gboolean FsRtlGetNextLargeMcbEntry_traverse_func
 302                 (struct run *run /* _key */,struct run *run_value,struct FsRtlGetNextLargeMcbEntry_input *input)
 303 {
 304         g_return_val_if_fail(run!=NULL,TRUE);
 305         g_return_val_if_fail(run_value!=NULL,TRUE);
 306         g_return_val_if_fail(run==run_value,TRUE);
 307         g_return_val_if_fail(input!=NULL,TRUE);
 308
 309         if (input->RunIndex_remaining>0) {
 310                 /* FIXME: performance: non-linear direct seek to the requested RunIndex */
 311                 input->RunIndex_remaining--;
 312                 if (input->RunIndex_remaining==0)
 313                         input->run_found_lower=run;
 314                 else
 315                         input->RunIndex_remaining--;
 316                 return FALSE;   /* continue the traversal */
 317                 }
 318
 319         if (input->run_found_lower)
 320                 input->run_found_higher=run;
 321         else
 322                 input->run_found=run;
 323         return TRUE;    /* stop the traversal */
 324 }
 325
 326
 327 /**
 328  * FsRtlGetNextLargeMcbEntry:
 329  * @Mcb: #PLARGE_MCB initialized by FsRtlInitializeLargeMcb().
 330  * %NULL value is forbidden.
 331  * @RunIndex: Requested range index to retrieve.
 332  * @Vbn: Returns the starting virtual block number of the wished range.
 333  * %NULL pointer is forbidden.
 334  * @Lbn: Returns the starting logical block number of the wished range (or -1 if it is a hole).
 335  * %NULL pointer is forbidden.
 336  * @SectorCount: Returns the length of the wished range.
 337  * %NULL pointer is forbidden.
 338  * Value less or equal to %0 is forbidden; FIXME: Is it W32 compliant?
 339  *
 340  * Retrieves the parameters of the specified run with index @RunIndex.
 341  * First real mapping run is numbered by %0, the next real mapping run is numbered %2 etc.
 342  * Odd run numbers are reserved for the holes between; libcaptive does not store them to its #GTree
 343  * and their parameters are calculated automatically from the neighbour runs. Such 'hole' runs
 344  * will be returned with @Lbn value %-1.
 345  *
 346  * Returns: %TRUE if successful.
 347  */
 348 BOOLEAN FsRtlGetNextLargeMcbEntry
 349                 (IN PLARGE_MCB Mcb,IN ULONG RunIndex,OUT PLONGLONG Vbn,OUT PLONGLONG Lbn,OUT PLONGLONG SectorCount)
 350 {
 351 struct Mcb_priv *Mcb_priv;
 352 struct FsRtlGetNextLargeMcbEntry_input input;
 353
 354         g_return_val_if_fail(Mcb!=NULL,FALSE);
 355         g_return_val_if_fail(Vbn!=NULL,FALSE);
 356         g_return_val_if_fail(Lbn!=NULL,FALSE);
 357         g_return_val_if_fail(SectorCount!=NULL,FALSE);
 358
 359         Mcb_hash_init();
 360         Mcb_priv=g_hash_table_lookup(Mcb_hash,Mcb);
 361         g_return_val_if_fail(Mcb_priv!=NULL,FALSE);
 362
 363         input.RunIndex_remaining=RunIndex;
 364         input.run_found=NULL;
 365         input.run_found_lower=NULL;
 366         input.run_found_higher=NULL;
 367         g_tree_foreach(Mcb_priv->gtree,(GTraverseFunc)FsRtlGetNextLargeMcbEntry_traverse_func,&input);
 368
 369         if (input.run_found) {
 370                 g_assert((RunIndex%2)==0);      /* search for mapping */
 371                 g_assert(input.run_found_lower ==NULL);
 372                 g_assert(input.run_found_higher==NULL);
 373                 *Vbn        =input.run_found->Vbn_start;
 374                 *Lbn        =input.run_found->Lbn_start;
 375                 *SectorCount=input.run_found->Vbn_end-input.run_found->Vbn_start;
 376                 return TRUE;
 377                 }
 378
 379         if (input.run_found_lower) {
 380                 g_assert((RunIndex%2)==1);      /* search for hole */
 381                 g_assert(input.run_found_higher!=NULL);
 382                 *Vbn        =input.run_found_lower->Vbn_end;
 383                 *Lbn        =-1;
 384                 *SectorCount=input.run_found_higher->Vbn_start-input.run_found_lower->Vbn_end;
 385                 return TRUE;
 386                 }
 387
 388         g_assert(input.run_found_higher==NULL);
 389         return FALSE;
 390 }
 391
 392
 393 struct FsRtlLookupLargeMcbEntry_input {
 394         LONGLONG Vbn;
 395         ULONG RunIndex;
 396         struct run *run_found;
 397         struct run *run_found_lower,*run_found_higher;
 398         };
 399
 400 static gboolean FsRtlLookupLargeMcbEntry_traverse_func
 401                 (struct run *run /* _key */,struct run *run_value,struct FsRtlLookupLargeMcbEntry_input *input)
 402 {
 403         g_return_val_if_fail(run!=NULL,TRUE);
 404         g_return_val_if_fail(run_value!=NULL,TRUE);
 405         g_return_val_if_fail(run==run_value,TRUE);
 406         g_return_val_if_fail(input!=NULL,TRUE);
 407
 408         if (run->Vbn_start<=input->Vbn && input->Vbn<run->Vbn_end) {
 409                 input->run_found=run;
 410                 input->run_found_lower=NULL;
 411                 return TRUE;    /* stop the traversal; hit */
 412                 }
 413         if (run->Vbn_end<=input->Vbn) {
 414                 input->run_found_lower=run;
 415                 input->RunIndex+=2;
 416                 return FALSE;   /* continue the traversal; not yet crossed by the run */
 417                 }
 418         if (input->Vbn<run->Vbn_start) {
 419                 input->run_found_higher=run;
 420                 input->RunIndex+=1;
 421                 return TRUE;    /* stop the traversal; the run skipped us */
 422                 }
 423         g_assert_not_reached();
 424         return TRUE;    /* stop the traversal */
 425 }
 426
 427
 428 /**
 429  * FsRtlLookupLargeMcbEntry:
 430  * @Mcb: #PLARGE_MCB initialized by FsRtlInitializeLargeMcb().
 431  * %NULL value is forbidden.
 432  * @Vbn: Starting virtual block number of the requested sector.
 433  * @Lbn: Returns the logical block number corresponding to @Vbn (or -1 if it is a hole).
 434  * %NULL value is permitted.
 435  * @SectorCountFromLbn: Returns the number of sectors after @Vbn in the mapping found.
 436  * FIXME: 'after' means including current 'Lbn' or without it?
 437  * %NULL value is permitted.
 438  * @StartingLbn: Returns the first logical block number of the mapping found (or -1 if it is a hole).
 439  * %NULL value is permitted.
 440  * @SectorCountFromStartingLbn: Returns total length in blocks of the mapping found.
 441  * %NULL value is permitted.
 442  * @Index: Returns the range index of the mapping found.
 443  * %NULL value is permitted.
 444  *
 445  * Retrieves the information about the requested virtual block number @Vbn
 446  * and its mapping (either real mapping or the hole).
 447  * First real mapping run is numbered by %0, the next real mapping run is numbered %2 etc.
 448  * Odd run numbers are reserved for the holes between; libcaptive does not store them to its #GTree
 449  * and their parameters are calculated automatically from the neighbour runs. Such 'hole' runs
 450  * will be returned with @Lbn value %-1.
 451  *
 452  * Returns: %TRUE if successful.
 453  */
 454 BOOLEAN FsRtlLookupLargeMcbEntry(IN PLARGE_MCB Mcb,IN LONGLONG Vbn,
 455                 OUT PLONGLONG Lbn OPTIONAL,
 456                 OUT PLONGLONG SectorCountFromLbn OPTIONAL,
 457                 OUT PLONGLONG StartingLbn OPTIONAL,
 458                 OUT PLONGLONG SectorCountFromStartingLbn OPTIONAL,
 459                 OUT PULONG Index OPTIONAL)
 460 {
 461 struct Mcb_priv *Mcb_priv;
 462 struct FsRtlLookupLargeMcbEntry_input input;
 463
 464         g_return_val_if_fail(Mcb!=NULL,FALSE);
 465
 466         Mcb_hash_init();
 467         Mcb_priv=g_hash_table_lookup(Mcb_hash,Mcb);
 468         g_return_val_if_fail(Mcb_priv!=NULL,FALSE);
 469
 470         input.Vbn=Vbn;
 471         input.RunIndex=0;
 472         input.run_found=NULL;
 473         input.run_found_lower=NULL;
 474         input.run_found_higher=NULL;
 475         g_tree_foreach(Mcb_priv->gtree,(GTraverseFunc)FsRtlLookupLargeMcbEntry_traverse_func,&input);
 476
 477         if (input.run_found) {
 478                 g_assert((input.RunIndex%2)==0);        /* hit the mapping */
 479                 g_assert(input.run_found_lower ==NULL);
 480                 g_assert(input.run_found_higher==NULL);
 481                 if (Lbn)
 482                         *Lbn=input.run_found->Lbn_start+(Vbn-input.run_found->Vbn_start);
 483                 if (SectorCountFromLbn) /* FIXME: 'after' means including current 'Lbn' or without it? */
 484                         *SectorCountFromLbn=input.run_found->Vbn_end-Vbn;
 485                 if (StartingLbn)
 486                         *StartingLbn=input.run_found->Lbn_start;
 487                 if (SectorCountFromStartingLbn)
 488                         *SectorCountFromStartingLbn=input.run_found->Vbn_end-input.run_found->Vbn_start;
 489                 if (Index)
 490                         *Index=input.RunIndex;
 491                 return TRUE;
 492                 }
 493
 494         if (input.run_found_lower) {
 495                 g_assert((input.RunIndex%2)==1);        /* search for hole */
 496                 g_assert(input.run_found_higher!=NULL);
 497                 if (Lbn)
 498                         *Lbn=-1;
 499                 if (SectorCountFromLbn) /* FIXME: 'after' means including current 'Lbn' or without it? */
 500                         *SectorCountFromLbn=input.run_found_higher->Vbn_start-Vbn;
 501                 if (StartingLbn)
 502                         *StartingLbn=-1;
 503                 if (SectorCountFromStartingLbn)
 504                         *SectorCountFromStartingLbn=input.run_found_higher->Vbn_start-input.run_found_lower->Vbn_end;
 505                 if (Index)
 506                         *Index=input.RunIndex;
 507                 return TRUE;
 508                 }
 509
 510         g_assert(input.run_found_higher==NULL);
 511         return FALSE;
 512 }
 513
 514
 515 /**
 516  * FsRtlLookupLastLargeMcbEntry:
 517  * @Mcb: #PLARGE_MCB initialized by FsRtlInitializeLargeMcb().
 518  * %NULL value is forbidden.
 519  * @Vbn: Returns the virtual block number of the last mapped sector.
 520  * %NULL pointer is forbidden.
 521  * @Lbn: Returns the logical block number of the last mapped sector.
 522  * %NULL pointer is forbidden.
 523  *
 524  * Retrieves the mapping of the ever last sector mapped by @Mcb.
 525  * FIXME: W32 doc says the returned @Lbn may get value %-1 but such 'hole' is not
 526  * a real mapping - why not to return the previous real mapping instead?
 527  * How can be some trailing 'hole's present?
 528  *
 529  * Returns: %TRUE if successful. %FALSE if @Mcb is empty.
 530  */
 531 BOOLEAN FsRtlLookupLastLargeMcbEntry(IN PLARGE_MCB Mcb,OUT PLONGLONG Vbn,OUT PLONGLONG Lbn)
 532 {
 533 struct Mcb_priv *Mcb_priv;
 534 struct run needle_run,*found_run;
 535
 536         g_return_val_if_fail(Mcb!=NULL,FALSE);
 537         g_return_val_if_fail(Vbn!=NULL,FALSE);
 538         g_return_val_if_fail(Lbn!=NULL,FALSE);
 539
 540         Mcb_hash_init();
 541         Mcb_priv=g_hash_table_lookup(Mcb_hash,Mcb);
 542         g_return_val_if_fail(Mcb_priv!=NULL,FALSE);
 543
 544         needle_run.Vbn_start=G_MAXINT64-1;
 545         needle_run.Vbn_end=G_MAXINT64;
 546
 547         run_compare_func_last_a_run=NULL;
 548         run_compare_func_last_b_run=NULL;
 549         found_run=g_tree_lookup(Mcb_priv->gtree,&needle_run);
 550         g_assert(found_run==NULL);
 551
 552         if (run_compare_func_last_a_run==NULL) {
 553                 g_assert(run_compare_func_last_b_run==NULL);
 554                 g_assert(g_tree_nnodes(Mcb_priv->gtree)==0);
 555
 556                 *Vbn=-1;
 557                 *Lbn=-1;
 558                 return FALSE;
 559                 }
 560         g_assert(run_compare_func_last_a_run!=&needle_run);
 561         g_assert(run_compare_func_last_b_run==&needle_run);
 562
 563         *Vbn=run_compare_func_last_a_run->Vbn_end-1;
 564         *Lbn=run_compare_func_last_a_run->Lbn_start
 565                         +((run_compare_func_last_a_run->Vbn_end-1)-run_compare_func_last_a_run->Vbn_start);
 566         return TRUE;
 567 }
 568
 569
 570 /**
 571  * FsRtlNumberOfRunsInLargeMcb:
 572  * @Mcb: #PLARGE_MCB initialized by FsRtlInitializeLargeMcb().
 573  * %NULL value is forbidden.
 574  *
 575  * Counts the number of runs mapped by @Mcb.
 576  *
 577  * Returns: The sum of 'real' and 'hole' runs in @Mcb.
 578  * libcaptive stores only 'real' runs in its #GTree therefore it returns value 2*real_runs-1.
 579  * Returns value %0 if @Mcb is empty.
 580  */
 581 ULONG FsRtlNumberOfRunsInLargeMcb(IN PLARGE_MCB Mcb)
 582 {
 583 struct Mcb_priv *Mcb_priv;
 584 gint nodes;
 585
 586         g_return_val_if_fail(Mcb!=NULL,0);
 587
 588         Mcb_hash_init();
 589         Mcb_priv=g_hash_table_lookup(Mcb_hash,Mcb);
 590         g_return_val_if_fail(Mcb_priv!=NULL,0);
 591
 592         nodes=g_tree_nnodes(Mcb_priv->gtree);
 593
 594         if (!nodes)
 595                 return 0;
 596         return nodes*2-1;       /* include holes as 'runs' */
 597 }
 598
 599
 600 struct FsRtlSplitLargeMcb_input {
 601         LONGLONG Vbn;
 602         LONGLONG Amount;
 603         struct Mcb_priv *Mcb_priv;
 604         struct run *insert_lower_run;   /* 'run' to insert after g_tree_foreach() finishes */
 605         };
 606
 607 static gboolean FsRtlSplitLargeMcb_traverse_func
 608                 (struct run *run /* _key */,struct run *run_value,struct FsRtlSplitLargeMcb_input *input)
 609 {
 610         g_return_val_if_fail(run!=NULL,TRUE);
 611         g_return_val_if_fail(run_value!=NULL,TRUE);
 612         g_return_val_if_fail(run==run_value,TRUE);
 613         g_return_val_if_fail(input!=NULL,TRUE);
 614
 615         /* unaffected run? */
 616         /* FIXME: performance: effective skip of all 'lower' runs without traversing them */
 617         if (input->Vbn>=run->Vbn_end)
 618                 return FALSE;   /* continue the traversal */
 619
 620         /* crossing run to be split?
 621          * 'lower_run' is created on the original place; just shortened.
 622          * current 'run' is shifted up later
 623          */
 624         if (input->Vbn<run->Vbn_end) {
 625 struct run *lower_run;
 626
 627                 captive_new(lower_run);
 628                 *lower_run=*run;
 629                 lower_run->Vbn_end=input->Vbn;
 630                 /* FIXME: shift 'run->Lbn_start' ? */
 631                 run->Vbn_start=input->Vbn;
 632
 633                 input->insert_lower_run=lower_run;
 634                 }
 635
 636         /* Shift the current 'run'.
 637          * Ordering is not changed in GTree so I hope I do not need to reinsert it.
 638          */
 639         run->Vbn_start+=input->Amount;
 640         g_assert(run->Vbn_end+input->Amount>run->Vbn_end);      /* overflow? */
 641         run->Vbn_end+=input->Amount;
 642         /* FIXME: shift 'run->Lbn_start' ? */
 643
 644         return FALSE;   /* continue the traversal */
 645 }
 646
 647
 648 /**
 649  * FsRtlSplitLargeMcb:
 650  * @Mcb: #PLARGE_MCB initialized by FsRtlInitializeLargeMcb().
 651  * %NULL value is forbidden.
 652  * @Vbn: First virtual block number of blocks to shift up.
 653  * @Amount: The amount of sectors to shift the blocks up by.
 654  * Value less or equal to %0 is forbidden; FIXME: Is it W32 compliant?
 655  *
 656  * Takes the range of existing @Vbn..infinity 'real' block runs and shifts their
 657  * virtual block numbers up by @Amount. Any possible 'real' run crossed by @Vbn
 658  * threshold value gets split with the 'hole' of size @Amount blocks.
 659  *
 660  * FIXME: W32 doc does not say if logical block number should be also shifted.
 661  * libcaptive does not touch logical block numbers.
 662  *
 663  * Returns: %TRUE if we crossed some 'real' run and we needed to create new 'hole'.
 664  * We still may map a lot of 'real' runs and return %FALSE if no such run will be hit by @Vbn directly.
 665  */
 666 BOOLEAN FsRtlSplitLargeMcb(IN PLARGE_MCB Mcb,IN LONGLONG Vbn,IN LONGLONG Amount)
 667 {
 668 struct Mcb_priv *Mcb_priv;
 669 struct FsRtlSplitLargeMcb_input input;
 670
 671         g_return_val_if_fail(Mcb!=NULL,FALSE);
 672         g_return_val_if_fail(Amount>0,FALSE);
 673
 674         Mcb_hash_init();
 675         Mcb_priv=g_hash_table_lookup(Mcb_hash,Mcb);
 676         g_return_val_if_fail(Mcb_priv!=NULL,FALSE);
 677
 678         input.Vbn=Vbn;
 679         input.Amount=Amount;
 680         input.insert_lower_run=NULL;
 681         input.Mcb_priv=Mcb_priv;
 682         g_tree_foreach(Mcb_priv->gtree,(GTraverseFunc)FsRtlSplitLargeMcb_traverse_func,&input);
 683
 684         if (input.insert_lower_run)
 685                 g_tree_insert(input.Mcb_priv->gtree,input.insert_lower_run,input.insert_lower_run);
 686
 687         return (input.insert_lower_run!=NULL);  /* the hole was successfuly created? */
 688 }
 689
 690
 691 /**
 692  * FsRtlTruncateLargeMcb:
 693  * @Mcb: #PLARGE_MCB initialized by FsRtlInitializeLargeMcb().
 694  * %NULL value is forbidden.
 695  * @Vbn: First virtual block number of blocks to delete.
 696  *
 697  * Deletes the mapping from @Vbn upwards. If no such blocks exist this function
 698  * does a safe NOP.
 699  */
 700 VOID FsRtlTruncateLargeMcb(IN PLARGE_MCB Mcb,IN LONGLONG Vbn)
 701 {
 702         g_return_if_fail(Mcb!=NULL);
 703
 704         FsRtlRemoveLargeMcbEntry(Mcb,Vbn,G_MAXINT64-Vbn+1);
 705 }