git.sur5r.net Git - bacula/bacula/blob - bacula/src/stored/match_bsr.c

   1 /*
   2    Bacula® - The Network Backup Solution
   3
   4    Copyright (C) 2002-2007 Free Software Foundation Europe e.V.
   5
   6    The main author of Bacula is Kern Sibbald, with contributions from
   7    many others, a complete list can be found in the file AUTHORS.
   8    This program is Free Software; you can redistribute it and/or
   9    modify it under the terms of version two of the GNU General Public
  10    License as published by the Free Software Foundation and included
  11    in the file LICENSE.
  12
  13    This program is distributed in the hope that it will be useful, but
  14    WITHOUT ANY WARRANTY; without even the implied warranty of
  15    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  16    General Public License for more details.
  17
  18    You should have received a copy of the GNU General Public License
  19    along with this program; if not, write to the Free Software
  20    Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
  21    02110-1301, USA.
  22
  23    Bacula® is a registered trademark of Kern Sibbald.
  24    The licensor of Bacula is the Free Software Foundation Europe
  25    (FSFE), Fiduciary Program, Sumatrastrasse 25, 8006 Zürich,
  26    Switzerland, email:ftf@fsfeurope.org.
  27 */
  28 /*
  29  *   Match Bootstrap Records (used for restores) against
  30  *     Volume Records
  31  *
  32  *     Kern Sibbald, June MMII
  33  *
  34  *   Version $Id$
  35  */
  36
  37 /*
  38  * ***FIXME***
  39  * find_smallest_volfile needs to be fixed to only look at items that
  40  *   are not marked as done.  Otherwise, it can find a bsr
  41  *   that has already been consumed, and this will cause the
  42  *   bsr to be used, thus we may seek back and re-read the
  43  *   same records, causing an error.  This deficiency must
  44  *   be fixed.  For the moment, it has been kludged in
  45  *   read_record.c to avoid seeking back if find_next_bsr
  46  *   returns a bsr pointing to a smaller address (file/block).
  47  *
  48  * Also for efficiency, once a bsr is done, it really should be
  49  *   delinked from the bsr chain.  This will avoid the above
  50  *   problem and make traversal of the bsr chain more efficient.
  51  *
  52  *   To be done ...
  53  */
  54
  55 #include "bacula.h"
  56 #include "stored.h"
  57 #ifdef HAVE_FNMATCH
  58 #include <fnmatch.h>
  59 #else
  60 #include "lib/fnmatch.h"
  61 #endif
  62
  63 const int dbglevel = 500;
  64
  65 /* Forward references */
  66 static int match_volume(BSR *bsr, BSR_VOLUME *volume, VOLUME_LABEL *volrec, bool done);
  67 static int match_sesstime(BSR *bsr, BSR_SESSTIME *sesstime, DEV_RECORD *rec, bool done);
  68 static int match_sessid(BSR *bsr, BSR_SESSID *sessid, DEV_RECORD *rec);
  69 static int match_client(BSR *bsr, BSR_CLIENT *client, SESSION_LABEL *sessrec, bool done);
  70 static int match_job(BSR *bsr, BSR_JOB *job, SESSION_LABEL *sessrec, bool done);
  71 static int match_job_type(BSR *bsr, BSR_JOBTYPE *job_type, SESSION_LABEL *sessrec, bool done);
  72 static int match_job_level(BSR *bsr, BSR_JOBLEVEL *job_level, SESSION_LABEL *sessrec, bool done);
  73 static int match_jobid(BSR *bsr, BSR_JOBID *jobid, SESSION_LABEL *sessrec, bool done);
  74 static int match_findex(BSR *bsr, BSR_FINDEX *findex, DEV_RECORD *rec, bool done);
  75 static int match_volfile(BSR *bsr, BSR_VOLFILE *volfile, DEV_RECORD *rec, bool done);
  76 static int match_stream(BSR *bsr, BSR_STREAM *stream, DEV_RECORD *rec, bool done);
  77 static int match_all(BSR *bsr, DEV_RECORD *rec, VOLUME_LABEL *volrec, SESSION_LABEL *sessrec, bool done);
  78 static int match_block_sesstime(BSR *bsr, BSR_SESSTIME *sesstime, DEV_BLOCK *block);
  79 static int match_block_sessid(BSR *bsr, BSR_SESSID *sessid, DEV_BLOCK *block);
  80 static BSR *find_smallest_volfile(BSR *fbsr, BSR *bsr);
  81
  82
  83 /*********************************************************************
  84  *
  85  *  If possible, position the archive device (tape) to read the
  86  *  next block.
  87  */
  88 void position_bsr_block(BSR *bsr, DEV_BLOCK *block)
  89 {
  90    /* To be implemented */
  91 }
  92
  93 /*********************************************************************
  94  *
  95  *  Do fast block rejection based on bootstrap records.
  96  *    use_fast_rejection will be set if we have VolSessionId and VolSessTime
  97  *    in each record. When BlockVer is >= 2, we have those in the block header
  98  *    so can do fast rejection.
  99  *
 100  *   returns:  1 if block may contain valid records
 101  *             0 if block may be skipped (i.e. it contains no records of
 102  *                  that can match the bsr).
 103  *
 104  */
 105 int match_bsr_block(BSR *bsr, DEV_BLOCK *block)
 106 {
 107    if (!bsr || !bsr->use_fast_rejection || (block->BlockVer < 2)) {
 108       return 1;                       /* cannot fast reject */
 109    }
 110
 111    for ( ; bsr; bsr=bsr->next) {
 112       if (!match_block_sesstime(bsr, bsr->sesstime, block)) {
 113          continue;
 114       }
 115       if (!match_block_sessid(bsr, bsr->sessid, block)) {
 116          continue;
 117       }
 118       return 1;
 119    }
 120    return 0;
 121 }
 122
 123 static int match_block_sesstime(BSR *bsr, BSR_SESSTIME *sesstime, DEV_BLOCK *block)
 124 {
 125    if (!sesstime) {
 126       return 1;                       /* no specification matches all */
 127    }
 128    if (sesstime->sesstime == block->VolSessionTime) {
 129       return 1;
 130    }
 131    if (sesstime->next) {
 132       return match_block_sesstime(bsr, sesstime->next, block);
 133    }
 134    return 0;
 135 }
 136
 137 static int match_block_sessid(BSR *bsr, BSR_SESSID *sessid, DEV_BLOCK *block)
 138 {
 139    if (!sessid) {
 140       return 1;                       /* no specification matches all */
 141    }
 142    if (sessid->sessid <= block->VolSessionId && sessid->sessid2 >= block->VolSessionId) {
 143       return 1;
 144    }
 145    if (sessid->next) {
 146       return match_block_sessid(bsr, sessid->next, block);
 147    }
 148    return 0;
 149 }
 150
 151
 152 /*********************************************************************
 153  *
 154  *      Match Bootstrap records
 155  *        returns  1 on match
 156  *        returns  0 no match and reposition is set if we should
 157  *                      reposition the tape
 158  *       returns -1 no additional matches possible
 159  */
 160 int match_bsr(BSR *bsr, DEV_RECORD *rec, VOLUME_LABEL *volrec, SESSION_LABEL *sessrec)
 161 {
 162    int stat;
 163
 164    /*
 165     * The bsr->reposition flag is set any time a bsr is done.
 166     *   In this case, we can probably reposition the
 167     *   tape to the next available bsr position.
 168     */
 169    if (bsr) {
 170       bsr->reposition = false;
 171       stat = match_all(bsr, rec, volrec, sessrec, true);
 172       /*
 173        * Note, bsr->reposition is set by match_all when
 174        *  a bsr is done. We turn it off if a match was
 175        *  found or if we cannot use positioning
 176        */
 177       if (stat != 0 || !bsr->use_positioning) {
 178          bsr->reposition = false;
 179       }
 180    } else {
 181       stat = 1;                       /* no bsr => match all */
 182    }
 183    return stat;
 184 }
 185
 186 /*
 187  * Find the next bsr that applies to the current tape.
 188  *   It is the one with the smallest VolFile position.
 189  */
 190 BSR *find_next_bsr(BSR *root_bsr, DEVICE *dev)
 191 {
 192    BSR *bsr;
 193    BSR *found_bsr = NULL;
 194
 195    /* Do tape/disk seeking only if CAP_POSITIONBLOCKS is on */
 196    if (!root_bsr) {
 197       Dmsg0(dbglevel, "NULL root bsr pointer passed to find_next_bsr.\n");
 198       return NULL;
 199    }
 200    if (!root_bsr->use_positioning ||
 201        !root_bsr->reposition || !dev->has_cap(CAP_POSITIONBLOCKS)) {
 202       Dmsg2(dbglevel, "No nxt_bsr use_pos=%d repos=%d\n", root_bsr->use_positioning, root_bsr->reposition);
 203       return NULL;
 204    }
 205    Dmsg2(dbglevel, "use_pos=%d repos=%d\n", root_bsr->use_positioning, root_bsr->reposition);
 206    root_bsr->mount_next_volume = false;
 207    /* Walk through all bsrs to find the next one to use => smallest file,block */
 208    for (bsr=root_bsr; bsr; bsr=bsr->next) {
 209       if (bsr->done || !match_volume(bsr, bsr->volume, &dev->VolHdr, 1)) {
 210          continue;
 211       }
 212       if (found_bsr == NULL) {
 213          found_bsr = bsr;
 214       } else {
 215          found_bsr = find_smallest_volfile(found_bsr, bsr);
 216       }
 217    }
 218    /*
 219     * If we get to this point and found no bsr, it means
 220     *  that any additional bsr's must apply to the next
 221     *  tape, so set a flag.
 222     */
 223    if (found_bsr == NULL) {
 224       root_bsr->mount_next_volume = true;
 225    }
 226    return found_bsr;
 227 }
 228
 229 /*
 230  * ***FIXME***
 231  * This routine needs to be fixed to only look at items that
 232  *   are not marked as done.  Otherwise, it can find a bsr
 233  *   that has already been consumed, and this will cause the
 234  *   bsr to be used, thus we may seek back and re-read the
 235  *   same records, causing an error.  This deficiency must
 236  *   be fixed.  For the moment, it has been kludged in
 237  *   read_record.c to avoid seeking back if find_next_bsr
 238  *   returns a bsr pointing to a smaller address (file/block).
 239  */
 240 static BSR *find_smallest_volfile(BSR *found_bsr, BSR *bsr)
 241 {
 242    BSR *return_bsr = found_bsr;
 243    BSR_VOLFILE *vf;
 244    BSR_VOLBLOCK *vb;
 245    uint32_t found_bsr_sfile, bsr_sfile;
 246    uint32_t found_bsr_sblock, bsr_sblock;
 247
 248    /* Find the smallest file in the found_bsr */
 249    vf = found_bsr->volfile;
 250    found_bsr_sfile = vf->sfile;
 251    while ( (vf=vf->next) ) {
 252       if (vf->sfile < found_bsr_sfile) {
 253          found_bsr_sfile = vf->sfile;
 254       }
 255    }
 256
 257    /* Find the smallest file in the bsr */
 258    vf = bsr->volfile;
 259    bsr_sfile = vf->sfile;
 260    while ( (vf=vf->next) ) {
 261       if (vf->sfile < bsr_sfile) {
 262          bsr_sfile = vf->sfile;
 263       }
 264    }
 265
 266    /* if the bsr file is less than the found_bsr file, return bsr */
 267    if (found_bsr_sfile > bsr_sfile) {
 268       return_bsr = bsr;
 269    } else if (found_bsr_sfile == bsr_sfile) {
 270       /* Files are equal */
 271       /* find smallest block in found_bsr */
 272       vb = found_bsr->volblock;
 273       found_bsr_sblock = vb->sblock;
 274       while ( (vb=vb->next) ) {
 275          if (vb->sblock < found_bsr_sblock) {
 276             found_bsr_sblock = vb->sblock;
 277          }
 278       }
 279       /* Find smallest block in bsr */
 280       vb = bsr->volblock;
 281       bsr_sblock = vb->sblock;
 282       while ( (vb=vb->next) ) {
 283          if (vb->sblock < bsr_sblock) {
 284             bsr_sblock = vb->sblock;
 285          }
 286       }
 287       /* Compare and return the smallest */
 288       if (found_bsr_sblock > bsr_sblock) {
 289          return_bsr = bsr;
 290       }
 291    }
 292    return return_bsr;
 293 }
 294
 295 /*
 296  * Called after the signature record so that
 297  *   we can see if the current bsr has been
 298  *   fully processed (i.e. is done).
 299  *  The bsr argument is not used, but is included
 300  *    for consistency with the other match calls.
 301  *
 302  * Returns: true if we should reposition
 303  *        : false otherwise.
 304  */
 305 bool is_this_bsr_done(BSR *bsr, DEV_RECORD *rec)
 306 {
 307    BSR *rbsr = rec->bsr;
 308    Dmsg1(dbglevel, "match_set %d\n", rbsr != NULL);
 309    if (!rbsr) {
 310       return false;
 311    }
 312    rec->bsr = NULL;
 313    rbsr->found++;
 314    if (rbsr->count && rbsr->found >= rbsr->count) {
 315       rbsr->done = true;
 316       rbsr->root->reposition = true;
 317       Dmsg2(dbglevel, "is_end_this_bsr set reposition=1 count=%d found=%d\n",
 318          rbsr->count, rbsr->found);
 319       return true;
 320    }
 321    return false;
 322 }
 323
 324 /*
 325  * Match all the components of current record
 326  *   returns  1 on match
 327  *   returns  0 no match
 328  *   returns -1 no additional matches possible
 329  */
 330 static int match_all(BSR *bsr, DEV_RECORD *rec, VOLUME_LABEL *volrec,
 331                      SESSION_LABEL *sessrec, bool done)
 332 {
 333    if (bsr->done) {
 334 //    Dmsg0(dbglevel, "bsr->done set\n");
 335       goto no_match;
 336    }
 337    if (!match_volume(bsr, bsr->volume, volrec, 1)) {
 338       Dmsg2(dbglevel, "bsr fail vol=%s != rec vol=%s\n", bsr->volume->VolumeName,
 339             volrec->VolumeName);
 340       goto no_match;
 341    }
 342    if (!match_volfile(bsr, bsr->volfile, rec, 1)) {
 343       Dmsg3(dbglevel, "Fail on file=%d. bsr=%d,%d\n",
 344          rec->File, bsr->volfile->sfile, bsr->volfile->efile);
 345       goto no_match;
 346    }
 347    if (!match_sesstime(bsr, bsr->sesstime, rec, 1)) {
 348       Dmsg2(dbglevel, "Fail on sesstime. bsr=%d rec=%d\n",
 349          bsr->sesstime->sesstime, rec->VolSessionTime);
 350       goto no_match;
 351    }
 352
 353    /* NOTE!! This test MUST come after the sesstime test */
 354    if (!match_sessid(bsr, bsr->sessid, rec)) {
 355       Dmsg2(dbglevel, "Fail on sessid. bsr=%d rec=%d\n",
 356          bsr->sessid->sessid, rec->VolSessionId);
 357       goto no_match;
 358    }
 359
 360    /* NOTE!! This test MUST come after sesstime and sessid tests */
 361    if (!match_findex(bsr, bsr->FileIndex, rec, 1)) {
 362       Dmsg3(dbglevel, "Fail on findex=%d. bsr=%d,%d\n",
 363          rec->FileIndex, bsr->FileIndex->findex, bsr->FileIndex->findex2);
 364       goto no_match;
 365    }
 366    /*
 367     * If a count was specified and we have a FileIndex, assume
 368     *   it is a Bacula created bsr (or the equivalent). We
 369     *   then save the bsr where the match occurred so that
 370     *   after processing the record or records, we can update
 371     *   the found count. I.e. rec->bsr points to the bsr that
 372     *   satisfied the match.
 373     */
 374    if (bsr->count && bsr->FileIndex) {
 375       rec->bsr = bsr;
 376       return 1;                       /* this is a complete match */
 377    }
 378
 379    /*
 380     * The selections below are not used by Bacula's
 381     *   restore command, and don't work because of
 382     *   the rec->bsr = bsr optimization above.
 383     */
 384    if (!match_jobid(bsr, bsr->JobId, sessrec, 1)) {
 385       Dmsg0(dbglevel, "fail on JobId\n");
 386       goto no_match;
 387
 388    }
 389    if (!match_job(bsr, bsr->job, sessrec, 1)) {
 390       Dmsg0(dbglevel, "fail on Job\n");
 391       goto no_match;
 392    }
 393    if (!match_client(bsr, bsr->client, sessrec, 1)) {
 394       Dmsg0(dbglevel, "fail on Client\n");
 395       goto no_match;
 396    }
 397    if (!match_job_type(bsr, bsr->JobType, sessrec, 1)) {
 398       Dmsg0(dbglevel, "fail on Job type\n");
 399       goto no_match;
 400    }
 401    if (!match_job_level(bsr, bsr->JobLevel, sessrec, 1)) {
 402       Dmsg0(dbglevel, "fail on Job level\n");
 403       goto no_match;
 404    }
 405    if (!match_stream(bsr, bsr->stream, rec, 1)) {
 406       Dmsg0(dbglevel, "fail on stream\n");
 407       goto no_match;
 408    }
 409    return 1;
 410
 411 no_match:
 412    if (bsr->next) {
 413       return match_all(bsr->next, rec, volrec, sessrec, bsr->done && done);
 414    }
 415    if (bsr->done && done) {
 416       return -1;
 417    }
 418    return 0;
 419 }
 420
 421 static int match_volume(BSR *bsr, BSR_VOLUME *volume, VOLUME_LABEL *volrec, bool done)
 422 {
 423    if (!volume) {
 424       return 0;                       /* Volume must match */
 425    }
 426    if (strcmp(volume->VolumeName, volrec->VolumeName) == 0) {
 427       return 1;
 428    }
 429    if (volume->next) {
 430       return match_volume(bsr, volume->next, volrec, 1);
 431    }
 432    return 0;
 433 }
 434
 435 static int match_client(BSR *bsr, BSR_CLIENT *client, SESSION_LABEL *sessrec, bool done)
 436 {
 437    if (!client) {
 438       return 1;                       /* no specification matches all */
 439    }
 440    if (strcmp(client->ClientName, sessrec->ClientName) == 0) {
 441       return 1;
 442    }
 443    if (client->next) {
 444       return match_client(bsr, client->next, sessrec, 1);
 445    }
 446    return 0;
 447 }
 448
 449 static int match_job(BSR *bsr, BSR_JOB *job, SESSION_LABEL *sessrec, bool done)
 450 {
 451    if (!job) {
 452       return 1;                       /* no specification matches all */
 453    }
 454    if (strcmp(job->Job, sessrec->Job) == 0) {
 455       return 1;
 456    }
 457    if (job->next) {
 458       return match_job(bsr, job->next, sessrec, 1);
 459    }
 460    return 0;
 461 }
 462
 463 static int match_job_type(BSR *bsr, BSR_JOBTYPE *job_type, SESSION_LABEL *sessrec, bool done)
 464 {
 465    if (!job_type) {
 466       return 1;                       /* no specification matches all */
 467    }
 468    if (job_type->JobType == sessrec->JobType) {
 469       return 1;
 470    }
 471    if (job_type->next) {
 472       return match_job_type(bsr, job_type->next, sessrec, 1);
 473    }
 474    return 0;
 475 }
 476
 477 static int match_job_level(BSR *bsr, BSR_JOBLEVEL *job_level, SESSION_LABEL *sessrec, bool done)
 478 {
 479    if (!job_level) {
 480       return 1;                       /* no specification matches all */
 481    }
 482    if (job_level->JobLevel == sessrec->JobLevel) {
 483       return 1;
 484    }
 485    if (job_level->next) {
 486       return match_job_level(bsr, job_level->next, sessrec, 1);
 487    }
 488    return 0;
 489 }
 490
 491 static int match_jobid(BSR *bsr, BSR_JOBID *jobid, SESSION_LABEL *sessrec, bool done)
 492 {
 493    if (!jobid) {
 494       return 1;                       /* no specification matches all */
 495    }
 496    if (jobid->JobId <= sessrec->JobId && jobid->JobId2 >= sessrec->JobId) {
 497       return 1;
 498    }
 499    if (jobid->next) {
 500       return match_jobid(bsr, jobid->next, sessrec, 1);
 501    }
 502    return 0;
 503 }
 504
 505 static int match_volfile(BSR *bsr, BSR_VOLFILE *volfile, DEV_RECORD *rec, bool done)
 506 {
 507    if (!volfile) {
 508       return 1;                       /* no specification matches all */
 509    }
 510    /* For the moment, these tests work only with tapes. */
 511    if (!(rec->state & REC_ISTAPE)) {
 512       return 1;                       /* All File records OK for this match */
 513    }
 514 // Dmsg3(dbglevel, "match_volfile: sfile=%d efile=%d recfile=%d\n",
 515 //             volfile->sfile, volfile->efile, rec->File);
 516    if (volfile->sfile <= rec->File && volfile->efile >= rec->File) {
 517       return 1;
 518    }
 519    /* Once we get past last efile, we are done */
 520    if (rec->File > volfile->efile) {
 521       volfile->done = true;              /* set local done */
 522    }
 523    if (volfile->next) {
 524       return match_volfile(bsr, volfile->next, rec, volfile->done && done);
 525    }
 526
 527    /* If we are done and all prior matches are done, this bsr is finished */
 528    if (volfile->done && done) {
 529       bsr->done = true;
 530       bsr->root->reposition = true;
 531       Dmsg2(dbglevel, "bsr done from volfile rec=%d volefile=%d\n",
 532          rec->File, volfile->efile);
 533    }
 534    return 0;
 535 }
 536
 537 static int match_stream(BSR *bsr, BSR_STREAM *stream, DEV_RECORD *rec, bool done)
 538 {
 539    if (!stream) {
 540       return 1;                       /* no specification matches all */
 541    }
 542    if (stream->stream == rec->Stream) {
 543       return 1;
 544    }
 545    if (stream->next) {
 546       return match_stream(bsr, stream->next, rec, 1);
 547    }
 548    return 0;
 549 }
 550
 551 static int match_sesstime(BSR *bsr, BSR_SESSTIME *sesstime, DEV_RECORD *rec, bool done)
 552 {
 553    if (!sesstime) {
 554       return 1;                       /* no specification matches all */
 555    }
 556    if (sesstime->sesstime == rec->VolSessionTime) {
 557       return 1;
 558    }
 559    if (rec->VolSessionTime > sesstime->sesstime) {
 560       sesstime->done = true;
 561    }
 562    if (sesstime->next) {
 563       return match_sesstime(bsr, sesstime->next, rec, sesstime->done && done);
 564    }
 565    if (sesstime->done && done) {
 566       bsr->done = true;
 567       bsr->root->reposition = true;
 568       Dmsg0(dbglevel, "bsr done from sesstime\n");
 569    }
 570    return 0;
 571 }
 572
 573 static int match_sessid(BSR *bsr, BSR_SESSID *sessid, DEV_RECORD *rec)
 574 {
 575    if (!sessid) {
 576       return 1;                       /* no specification matches all */
 577    }
 578    if (sessid->sessid <= rec->VolSessionId && sessid->sessid2 >= rec->VolSessionId) {
 579       return 1;
 580    }
 581    if (sessid->next) {
 582       return match_sessid(bsr, sessid->next, rec);
 583    }
 584    return 0;
 585 }
 586
 587 /*
 588  * When reading the Volume, the Volume Findex (rec->FileIndex) always
 589  *   are found in sequential order. Thus we can make optimizations.
 590  *
 591  *  ***FIXME*** optimizations
 592  * We could optimize a lot here by removing the recursion, and
 593  *   stopping the search earlier -- say when rec->FileIndex > findex->findex2
 594  *   and findex->next == NULL.
 595  */
 596 static int match_findex(BSR *bsr, BSR_FINDEX *findex, DEV_RECORD *rec, bool done)
 597 {
 598    if (!findex) {
 599       return 1;                       /* no specification matches all */
 600    }
 601    if (!findex->done) {
 602       if (findex->findex <= rec->FileIndex && findex->findex2 >= rec->FileIndex) {
 603          Dmsg3(dbglevel, "Match on findex=%d. bsr=%d,%d\n",
 604                rec->FileIndex, findex->findex, findex->findex2);
 605          return 1;
 606       }
 607       if (rec->FileIndex > findex->findex2) {
 608          findex->done = true;
 609       }
 610    }
 611    if (findex->next) {
 612       return match_findex(bsr, findex->next, rec, findex->done && done);
 613    }
 614    if (findex->done && done) {
 615       bsr->done = true;
 616       bsr->root->reposition = true;
 617       Dmsg1(dbglevel, "bsr done from findex %d\n", rec->FileIndex);
 618    }
 619    return 0;
 620 }