src/peer_select.cc

   1
   2 /*
   3  * $Id: peer_select.cc,v 1.92 1998/12/05 00:54:35 wessels Exp $
   4  *
   5  * DEBUG: section 44    Peer Selection Algorithm
   6  * AUTHOR: Duane Wessels
   7  *
   8  * SQUID Internet Object Cache  http://squid.nlanr.net/Squid/
   9  * ----------------------------------------------------------
  10  *
  11  *  Squid is the result of efforts by numerous individuals from the
  12  *  Internet community.  Development is led by Duane Wessels of the
  13  *  National Laboratory for Applied Network Research and funded by the
  14  *  National Science Foundation.  Squid is Copyrighted (C) 1998 by
  15  *  Duane Wessels and the University of California San Diego.  Please
  16  *  see the COPYRIGHT file for full details.  Squid incorporates
  17  *  software developed and/or copyrighted by other sources.  Please see
  18  *  the CREDITS file for full details.
  19  *
  20  *  This program is free software; you can redistribute it and/or modify
  21  *  it under the terms of the GNU General Public License as published by
  22  *  the Free Software Foundation; either version 2 of the License, or
  23  *  (at your option) any later version.
  24  *
  25  *  This program is distributed in the hope that it will be useful,
  26  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  27  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  28  *  GNU General Public License for more details.
  29  *
  30  *  You should have received a copy of the GNU General Public License
  31  *  along with this program; if not, write to the Free Software
  32  *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111, USA.
  33  *
  34  */
  35
  36 #include "squid.h"
  37
  38 const char *hier_strings[] =
  39 {
  40     "NONE",
  41     "DIRECT",
  42     "SIBLING_HIT",
  43     "PARENT_HIT",
  44     "DEFAULT_PARENT",
  45     "SINGLE_PARENT",
  46     "FIRST_UP_PARENT",
  47     "FIRST_PARENT_MISS",
  48     "CLOSEST_PARENT_MISS",
  49     "CLOSEST_PARENT",
  50     "CLOSEST_DIRECT",
  51     "NO_DIRECT_FAIL",
  52     "SOURCE_FASTEST",
  53     "ROUNDROBIN_PARENT",
  54 #if USE_CACHE_DIGESTS
  55     "CACHE_DIGEST_HIT",
  56 #endif
  57 #if USE_CARP
  58     "CARP",
  59 #endif
  60     "ANY_PARENT",
  61     "INVALID CODE"
  62 };
  63
  64 static struct {
  65     int timeouts;
  66 } PeerStats;
  67
  68 static char *DirectStr[] =
  69 {
  70     "DIRECT_UNKNOWN",
  71     "DIRECT_NO",
  72     "DIRECT_MAYBE",
  73     "DIRECT_YES"
  74 };
  75
  76 static void peerSelectFoo(ps_state *);
  77 static void peerPingTimeout(void *data);
  78 static void peerSelectCallback(ps_state * psstate);
  79 static IRCB peerHandlePingReply;
  80 static void peerSelectStateFree(ps_state * psstate);
  81 static void peerIcpParentMiss(peer *, icp_common_t *, ps_state *);
  82 #if USE_HTCP
  83 static void peerHtcpParentMiss(peer *, htcpReplyData *, ps_state *);
  84 static void peerHandleHtcpReply(peer *, peer_t, htcpReplyData *, void *);
  85 #endif
  86 static int peerCheckNetdbDirect(ps_state * psstate);
  87 static void peerGetSomeNeighbor(ps_state *);
  88 static void peerGetSomeNeighborReplies(ps_state *);
  89 static void peerGetSomeDirect(ps_state *);
  90 static void peerGetSomeParent(ps_state *);
  91 static void psstateFigureDirect(ps_state *);
  92 static void peerAddFwdServer(FwdServer **, peer *, hier_code);
  93
  94 static void
  95 peerSelectStateFree(ps_state * psstate)
  96 {
  97     if (psstate->acl_checklist) {
  98         debug(44, 1) ("calling aclChecklistFree() from peerSelectStateFree\n");
  99         aclChecklistFree(psstate->acl_checklist);
 100     }
 101     requestUnlink(psstate->request);
 102     psstate->request = NULL;
 103     if (psstate->entry) {
 104         assert(psstate->entry->ping_status != PING_WAITING);
 105         storeUnlockObject(psstate->entry);
 106         psstate->entry = NULL;
 107     }
 108     cbdataFree(psstate);
 109 }
 110
 111 int
 112 peerSelectIcpPing(request_t * request, int direct, StoreEntry * entry)
 113 {
 114     int n;
 115     assert(entry);
 116     assert(entry->ping_status == PING_NONE);
 117     assert(direct != DIRECT_YES);
 118     debug(44, 3) ("peerSelectIcpPing: %s\n", storeUrl(entry));
 119     if (!request->flags.hierarchical && direct != DIRECT_NO)
 120         return 0;
 121     if (EBIT_TEST(entry->flags, KEY_PRIVATE) && !neighbors_do_private_keys)
 122         if (direct != DIRECT_NO)
 123             return 0;
 124     n = neighborsCount(request);
 125     debug(44, 3) ("peerSelectIcpPing: counted %d neighbors\n", n);
 126     return n;
 127 }
 128
 129
 130 void
 131 peerSelect(request_t * request,
 132     StoreEntry * entry,
 133     PSC * callback,
 134     void *callback_data)
 135 {
 136     ps_state *psstate = xcalloc(1, sizeof(ps_state));
 137     if (entry)
 138         debug(44, 3) ("peerSelect: %s\n", storeUrl(entry));
 139     else
 140         debug(44, 3) ("peerSelect: %s\n", RequestMethodStr[request->method]);
 141     cbdataAdd(psstate, cbdataXfree, 0);
 142     psstate->request = requestLink(request);
 143     psstate->entry = entry;
 144     psstate->callback = callback;
 145     psstate->callback_data = callback_data;
 146     psstate->direct = DIRECT_UNKNOWN;
 147 #if USE_CACHE_DIGESTS
 148     request->hier.peer_select_start = current_time;
 149 #endif
 150     if (psstate->entry)
 151         storeLockObject(psstate->entry);
 152     cbdataLock(callback_data);
 153     peerSelectFoo(psstate);
 154 }
 155
 156 static void
 157 peerCheckNeverDirectDone(int answer, void *data)
 158 {
 159     ps_state *psstate = data;
 160     psstate->acl_checklist = NULL;
 161     debug(44, 3) ("peerCheckNeverDirectDone: %d\n", answer);
 162     psstate->never_direct = answer ? 1 : -1;
 163     peerSelectFoo(psstate);
 164 }
 165
 166 static void
 167 peerCheckAlwaysDirectDone(int answer, void *data)
 168 {
 169     ps_state *psstate = data;
 170     psstate->acl_checklist = NULL;
 171     debug(44, 3) ("peerCheckAlwaysDirectDone: %d\n", answer);
 172     psstate->always_direct = answer ? 1 : -1;
 173     peerSelectFoo(psstate);
 174 }
 175
 176 static void
 177 peerSelectCallback(ps_state * psstate)
 178 {
 179     StoreEntry *entry = psstate->entry;
 180     FwdServer *fs = psstate->servers;
 181     void *data = psstate->callback_data;
 182     if (entry) {
 183         debug(44, 3) ("peerSelectCallback: %s\n", storeUrl(entry));
 184         if (entry->ping_status == PING_WAITING)
 185             eventDelete(peerPingTimeout, psstate);
 186         entry->ping_status = PING_DONE;
 187     }
 188     if (fs == NULL) {
 189         debug(44, 1) ("Failed to select source for '%s'\n", storeUrl(entry));
 190         debug(44, 1) ("  always_direct = %d\n", psstate->always_direct);
 191         debug(44, 1) ("   never_direct = %d\n", psstate->never_direct);
 192         debug(44, 1) ("       timedout = %d\n", psstate->ping.timedout);
 193     }
 194     psstate->ping.stop = current_time;
 195     if (cbdataValid(data)) {
 196         psstate->servers = NULL;
 197         psstate->callback(fs, data);
 198     }
 199     cbdataUnlock(data);
 200     peerSelectStateFree(psstate);
 201 }
 202
 203 static int
 204 peerCheckNetdbDirect(ps_state * psstate)
 205 {
 206     peer *p = whichPeer(&psstate->closest_parent_miss);
 207     int myrtt;
 208     int myhops;
 209     if (p == NULL)
 210         return 0;
 211     myrtt = netdbHostRtt(psstate->request->host);
 212     debug(44, 3) ("peerCheckNetdbDirect: MY RTT = %d msec\n", myrtt);
 213     debug(44, 3) ("peerCheckNetdbDirect: closest_parent_miss RTT = %d msec\n",
 214         psstate->ping.p_rtt);
 215     if (myrtt && myrtt < psstate->ping.p_rtt)
 216         return 1;
 217     myhops = netdbHostHops(psstate->request->host);
 218     debug(44, 3) ("peerCheckNetdbDirect: MY hops = %d\n", myhops);
 219     debug(44, 3) ("peerCheckNetdbDirect: minimum_direct_hops = %d\n",
 220         Config.minDirectHops);
 221     if (myhops && myhops <= Config.minDirectHops)
 222         return 1;
 223     return 0;
 224 }
 225
 226 static void
 227 peerSelectFoo(ps_state * psstate)
 228 {
 229     StoreEntry *entry = psstate->entry;
 230     request_t *request = psstate->request;
 231     debug(44, 3) ("peerSelectFoo: '%s %s'\n",
 232         RequestMethodStr[request->method],
 233         request->host);
 234     if (psstate->direct == DIRECT_UNKNOWN) {
 235         psstateFigureDirect(psstate);
 236         if (psstate->direct == DIRECT_UNKNOWN)
 237             return;
 238     }
 239     if (entry->ping_status == PING_NONE) {
 240         peerGetSomeNeighbor(psstate);
 241         if (entry->ping_status == PING_WAITING)
 242             return;
 243     } else if (entry->ping_status == PING_WAITING) {
 244         peerGetSomeNeighborReplies(psstate);
 245         entry->ping_status = PING_DONE;
 246     }
 247     if (Config.onoff.prefer_direct)
 248         peerGetSomeDirect(psstate);
 249     peerGetSomeParent(psstate);
 250     if (!Config.onoff.prefer_direct)
 251         peerGetSomeDirect(psstate);
 252     peerSelectCallback(psstate);
 253 }
 254
 255 static void
 256 psstateFigureDirect(ps_state * psstate)
 257 {
 258     request_t *request = psstate->request;
 259     if (psstate->always_direct == 0 && Config.accessList.AlwaysDirect) {
 260         psstate->acl_checklist = aclChecklistCreate(
 261             Config.accessList.AlwaysDirect,
 262             request,
 263             request->client_addr,
 264             NULL,               /* user agent */
 265             NULL);              /* ident */
 266         aclNBCheck(psstate->acl_checklist,
 267             peerCheckAlwaysDirectDone,
 268             psstate);
 269         return;
 270     } else if (psstate->always_direct > 0) {
 271         psstate->direct = DIRECT_YES;
 272     } else if (psstate->never_direct == 0 && Config.accessList.NeverDirect) {
 273         psstate->acl_checklist = aclChecklistCreate(
 274             Config.accessList.NeverDirect,
 275             request,
 276             request->client_addr,
 277             NULL,               /* user agent */
 278             NULL);              /* ident */
 279         aclNBCheck(psstate->acl_checklist,
 280             peerCheckNeverDirectDone,
 281             psstate);
 282         return;
 283     } else if (psstate->never_direct > 0) {
 284         psstate->direct = DIRECT_NO;
 285     } else if (request->flags.loopdetect) {
 286         psstate->direct = DIRECT_YES;
 287     } else {
 288         psstate->direct = DIRECT_MAYBE;
 289     }
 290     debug(44, 3) ("psstateFigureDirect: direct = %s\n",
 291         DirectStr[psstate->direct]);
 292 }
 293
 294 /*
 295  * peerGetSomeNeighbor
 296  *
 297  * Selects a neighbor (parent or sibling) based on one of the
 298  * following methods:
 299  *      Cache Digests
 300  *      CARP
 301  *      Netdb RTT estimates
 302  *      ICP/HTCP queries
 303  */
 304 static void
 305 peerGetSomeNeighbor(ps_state * ps)
 306 {
 307     StoreEntry *entry = ps->entry;
 308     request_t *request = ps->request;
 309     peer *p;
 310     hier_code code = HIER_NONE;
 311     assert(entry->ping_status == PING_NONE);
 312     if (ps->direct == DIRECT_YES) {
 313         entry->ping_status = PING_DONE;
 314         return;
 315     }
 316 #if USE_CACHE_DIGESTS
 317     if ((p = neighborsDigestSelect(request, entry))) {
 318         code = CACHE_DIGEST_HIT;
 319     } else
 320 #endif
 321 #if USE_CARP
 322     if ((p = carpSelectParent(request))) {
 323         code = CARP;
 324     } else
 325 #endif
 326     if ((p = netdbClosestParent(request))) {
 327         code = CLOSEST_PARENT;
 328     } else if (peerSelectIcpPing(request, ps->direct, entry)) {
 329         debug(44, 3) ("peerSelect: Doing ICP pings\n");
 330         ps->ping.start = current_time;
 331         ps->ping.n_sent = neighborsUdpPing(request,
 332             entry,
 333             peerHandlePingReply,
 334             ps,
 335             &ps->ping.n_replies_expected,
 336             &ps->ping.timeout);
 337         if (ps->ping.n_sent == 0)
 338             debug(44, 0) ("WARNING: neighborsUdpPing returned 0\n");
 339         debug(44, 3) ("peerSelect: %d ICP replies expected, RTT %d msec\n",
 340             ps->ping.n_replies_expected, ps->ping.timeout);
 341         if (ps->ping.n_replies_expected > 0) {
 342             entry->ping_status = PING_WAITING;
 343             eventAdd("peerPingTimeout",
 344                 peerPingTimeout,
 345                 ps,
 346                 0.001 * ps->ping.timeout,
 347                 0);
 348             return;
 349         }
 350     }
 351     if (code != HIER_NONE) {
 352         assert(p);
 353         debug(44, 3) ("peerSelect: %s/%s\n", hier_strings[code], p->host);
 354         peerAddFwdServer(&ps->servers, p, code);
 355     }
 356     entry->ping_status = PING_DONE;
 357 }
 358
 359 /*
 360  * peerGetSomeNeighborReplies
 361  *
 362  * Selects a neighbor (parent or sibling) based on ICP/HTCP replies.
 363  */
 364 static void
 365 peerGetSomeNeighborReplies(ps_state * ps)
 366 {
 367     StoreEntry *entry = ps->entry;
 368     request_t *request = ps->request;
 369     peer *p = NULL;
 370     hier_code code = HIER_NONE;
 371     assert(entry->ping_status == PING_WAITING);
 372     assert(ps->direct != DIRECT_YES);
 373     if (peerCheckNetdbDirect(ps)) {
 374         code = CLOSEST_DIRECT;
 375         debug(44, 3) ("peerSelect: %s/%s\n", hier_strings[code], request->host);
 376         peerAddFwdServer(&ps->servers, NULL, code);
 377         return;
 378     }
 379     if ((p = ps->hit)) {
 380         code = ps->hit_type == PEER_PARENT ? PARENT_HIT : SIBLING_HIT;
 381     } else
 382 #if ALLOW_SOURCE_PING
 383     if ((p = ps->secho)) {
 384         code = SOURCE_FASTEST;
 385     } else
 386 #endif
 387     if (ps->closest_parent_miss.sin_addr.s_addr != any_addr.s_addr) {
 388         p = whichPeer(&ps->closest_parent_miss);
 389         code = CLOSEST_PARENT_MISS;
 390     } else if (ps->first_parent_miss.sin_addr.s_addr != any_addr.s_addr) {
 391         p = whichPeer(&ps->first_parent_miss);
 392         code = FIRST_PARENT_MISS;
 393     }
 394     if (p && code != HIER_NONE) {
 395         debug(44, 3) ("peerSelect: %s/%s\n", hier_strings[code], p->host);
 396         peerAddFwdServer(&ps->servers, p, code);
 397     }
 398 }
 399
 400
 401 /*
 402  * peerGetSomeDirect
 403  *
 404  * Simply adds a 'direct' entry to the FwdServers list if this
 405  * request can be forwarded directly to the origin server
 406  */
 407 static void
 408 peerGetSomeDirect(ps_state * ps)
 409 {
 410     if (ps->direct == DIRECT_NO)
 411         return;
 412     if (ps->request->protocol == PROTO_WAIS)
 413         /* Its not really DIRECT, now is it? */
 414         peerAddFwdServer(&ps->servers, Config.Wais.peer, DIRECT);
 415     else
 416         peerAddFwdServer(&ps->servers, NULL, DIRECT);
 417 }
 418
 419 static void
 420 peerGetSomeParent(ps_state * ps)
 421 {
 422     peer *p;
 423     request_t *request = ps->request;
 424     hier_code code = HIER_NONE;
 425     debug(44, 3) ("peerGetSomeParent: %s %s\n",
 426         RequestMethodStr[request->method],
 427         request->host);
 428     if ((p = getDefaultParent(request))) {
 429         code = DEFAULT_PARENT;
 430     } else if ((p = getRoundRobinParent(request))) {
 431         code = ROUNDROBIN_PARENT;
 432     } else if ((p = getFirstUpParent(request))) {
 433         code = FIRSTUP_PARENT;
 434     } else if ((p = getAnyParent(request))) {
 435         code = ANY_OLD_PARENT;
 436     }
 437     if (code != HIER_NONE) {
 438         debug(44, 3) ("peerSelect: %s/%s\n", hier_strings[code], p->host);
 439         peerAddFwdServer(&ps->servers, p, code);
 440     }
 441 }
 442
 443 static void
 444 peerPingTimeout(void *data)
 445 {
 446     ps_state *psstate = data;
 447     StoreEntry *entry = psstate->entry;
 448     if (entry)
 449         debug(44, 3) ("peerPingTimeout: '%s'\n", storeUrl(entry));
 450     entry->ping_status = PING_TIMEOUT;
 451     if (!cbdataValid(psstate->callback_data)) {
 452         /* request aborted */
 453         cbdataUnlock(psstate->callback_data);
 454         peerSelectStateFree(psstate);
 455         return;
 456     }
 457     PeerStats.timeouts++;
 458     psstate->ping.timedout = 1;
 459     peerSelectFoo(psstate);
 460 }
 461
 462 void
 463 peerSelectInit(void)
 464 {
 465     memset(&PeerStats, '\0', sizeof(PeerStats));
 466     assert(sizeof(hier_strings) == (HIER_MAX + 1) * sizeof(char *));
 467 }
 468
 469 static void
 470 peerIcpParentMiss(peer * p, icp_common_t * header, ps_state * ps)
 471 {
 472     int rtt;
 473     int hops;
 474     if (Config.onoff.query_icmp) {
 475         if (header->flags & ICP_FLAG_SRC_RTT) {
 476             rtt = header->pad & 0xFFFF;
 477             hops = (header->pad >> 16) & 0xFFFF;
 478             if (rtt > 0 && rtt < 0xFFFF)
 479                 netdbUpdatePeer(ps->request, p, rtt, hops);
 480             if (rtt && (ps->ping.p_rtt == 0 || rtt < ps->ping.p_rtt)) {
 481                 ps->closest_parent_miss = p->in_addr;
 482                 ps->ping.p_rtt = rtt;
 483             }
 484         }
 485     }
 486     /* if closest-only is set, then don't allow FIRST_PARENT_MISS */
 487     if (p->options.closest_only)
 488         return;
 489     /* set FIRST_MISS if there is no CLOSEST parent */
 490     if (ps->closest_parent_miss.sin_addr.s_addr != any_addr.s_addr)
 491         return;
 492     rtt = tvSubMsec(ps->ping.start, current_time) / p->weight;
 493     if (ps->ping.w_rtt == 0 || rtt < ps->ping.w_rtt) {
 494         ps->first_parent_miss = p->in_addr;
 495         ps->ping.w_rtt = rtt;
 496     }
 497 }
 498
 499 static void
 500 peerHandleIcpReply(peer * p, peer_t type, icp_common_t * header, void *data)
 501 {
 502     ps_state *psstate = data;
 503     icp_opcode op = header->opcode;
 504     debug(44, 3) ("peerHandleIcpReply: %s %s\n",
 505         icp_opcode_str[op],
 506         storeUrl(psstate->entry));
 507 #if USE_CACHE_DIGESTS && 0
 508     /* do cd lookup to count false misses */
 509     if (p && request)
 510         peerNoteDigestLookup(request, p,
 511             peerDigestLookup(p, request, psstate->entry));
 512 #endif
 513     psstate->ping.n_recv++;
 514     if (op == ICP_MISS || op == ICP_DECHO) {
 515         if (type == PEER_PARENT)
 516             peerIcpParentMiss(p, header, psstate);
 517     } else if (op == ICP_HIT) {
 518         psstate->hit = p;
 519         psstate->hit_type = type;
 520         peerSelectFoo(psstate);
 521         return;
 522     }
 523 #if ALLOW_SOURCE_PING
 524     else if (op == ICP_SECHO) {
 525         psstate->secho = p;
 526         peerSelectFoo(psstate);
 527         return;
 528     }
 529 #endif
 530     if (psstate->ping.n_recv < psstate->ping.n_replies_expected)
 531         return;
 532     peerSelectFoo(psstate);
 533 }
 534
 535 #if USE_HTCP
 536 static void
 537 peerHandleHtcpReply(peer * p, peer_t type, htcpReplyData * htcp, void *data)
 538 {
 539     ps_state *psstate = data;
 540     request_t *request = psstate->request;
 541     debug(44, 3) ("peerHandleIcpReply: %s %s\n",
 542         htcp->hit ? "HIT" : "MISS",
 543         storeUrl(psstate->entry));
 544     psstate->ping.n_recv++;
 545     if (htcp->hit) {
 546         psstate->hit = p;
 547         psstate->hit_type = type;
 548         peerSelectFoo(psstate);
 549         return;
 550     }
 551     if (type == PEER_PARENT)
 552         peerHtcpParentMiss(p, htcp, psstate);
 553     if (psstate->ping.n_recv < psstate->ping.n_replies_expected)
 554         return;
 555     peerSelectFoo(psstate);
 556 }
 557
 558 static void
 559 peerHtcpParentMiss(peer * p, htcpReplyData * htcp, ps_state * ps)
 560 {
 561     int rtt;
 562     int hops;
 563     if (Config.onoff.query_icmp) {
 564         if (htcp->cto.rtt > 0) {
 565             rtt = (int) htcp->cto.rtt * 1000;
 566             hops = (int) htcp->cto.hops * 1000;
 567             netdbUpdatePeer(ps->request, p, rtt, hops);
 568             if (rtt && (ps->ping.p_rtt == 0 || rtt < ps->ping.p_rtt)) {
 569                 ps->closest_parent_miss = p->in_addr;
 570                 ps->ping.p_rtt = rtt;
 571             }
 572         }
 573     }
 574     /* if closest-only is set, then don't allow FIRST_PARENT_MISS */
 575     if (p->options.closest_only)
 576         return;
 577     /* set FIRST_MISS if there is no CLOSEST parent */
 578     if (ps->closest_parent_miss.sin_addr.s_addr != any_addr.s_addr)
 579         return;
 580     rtt = tvSubMsec(ps->ping.start, current_time) / p->weight;
 581     if (ps->ping.w_rtt == 0 || rtt < ps->ping.w_rtt) {
 582         ps->first_parent_miss = p->in_addr;
 583         ps->ping.w_rtt = rtt;
 584     }
 585 }
 586 #endif
 587
 588 static void
 589 peerHandlePingReply(peer * p, peer_t type, protocol_t proto, void *pingdata, void *data)
 590 {
 591     if (proto == PROTO_ICP)
 592         peerHandleIcpReply(p, type, pingdata, data);
 593 #if USE_HTCP
 594     else if (proto == PROTO_HTCP)
 595         peerHandleHtcpReply(p, type, pingdata, data);
 596 #endif
 597     else
 598         debug(44, 1) ("peerHandlePingReply: unknown protocol_t %d\n", (int) proto);
 599 }
 600
 601 static void
 602 peerAddFwdServer(FwdServer ** FS, peer * p, hier_code code)
 603 {
 604     FwdServer *fs = memAllocate(MEM_FWD_SERVER);
 605     debug(44, 5) ("peerAddFwdServer: adding %s %s\n",
 606         p ? p->host : "DIRECT",
 607         hier_strings[code]);
 608     fs->peer = p;
 609     fs->code = code;
 610     cbdataLock(fs->peer);
 611     while (*FS)
 612         FS = &(*FS)->next;
 613     *FS = fs;
 614 }