src/runtime/cheneygc.c

   1 /*
   2  * stop and copy GC based on Cheney's algorithm
   3  */
   4
   5 /*
   6  * This software is part of the SBCL system. See the README file for
   7  * more information.
   8  *
   9  * This software is derived from the CMU CL system, which was
  10  * written at Carnegie Mellon University and released into the
  11  * public domain. The software is in the public domain and is
  12  * provided with absolutely no warranty. See the COPYING and CREDITS
  13  * files for more information.
  14  */
  15
  16 #include <stdio.h>
  17 #include <sys/time.h>
  18 #include <sys/resource.h>
  19 #include <signal.h>
  20 #include "sbcl.h"
  21 #include "runtime.h"
  22 #include "os.h"
  23 #include "gc.h"
  24 #include "gc-internal.h"
  25 #include "globals.h"
  26 #include "interrupt.h"
  27 #include "validate.h"
  28 #include "lispregs.h"
  29 #include "interr.h"
  30 #include "genesis/static-symbols.h"
  31 #include "genesis/primitive-objects.h"
  32 #include "thread.h"
  33 #include "arch.h"
  34
  35 /* So you need to debug? */
  36 #if 0
  37 #define PRINTNOISE
  38 #define DEBUG_SPACE_PREDICATES
  39 #define DEBUG_SCAVENGE_VERBOSE
  40 #define DEBUG_COPY_VERBOSE
  41 #define DEBUG_CODE_GC
  42 #endif
  43
  44 lispobj *from_space;
  45 lispobj *from_space_free_pointer;
  46
  47 lispobj *new_space;
  48 lispobj *new_space_free_pointer;
  49
  50 static void scavenge_newspace(void);
  51
  52 \f
  53 /* collecting garbage */
  54
  55 #ifdef PRINTNOISE
  56 static double
  57 tv_diff(struct timeval *x, struct timeval *y)
  58 {
  59     return (((double) x->tv_sec + (double) x->tv_usec * 1.0e-6) -
  60             ((double) y->tv_sec + (double) y->tv_usec * 1.0e-6));
  61 }
  62 #endif
  63
  64 #define BYTES_ZERO_BEFORE_END (1<<12)
  65
  66 /* FIXME do we need this?  Doesn't it duplicate lisp code in
  67  * scrub-control-stack? */
  68
  69 static void
  70 zero_stack(void)
  71 {
  72     lispobj *ptr = current_control_stack_pointer;
  73  search:
  74     do {
  75         if (*ptr)
  76             goto fill;
  77         ptr++;
  78     } while (((unsigned long)ptr) & (BYTES_ZERO_BEFORE_END-1));
  79     return;
  80  fill:
  81     do {
  82         *ptr++ = 0;
  83     } while (((unsigned long)ptr) & (BYTES_ZERO_BEFORE_END-1));
  84
  85     goto search;
  86 }
  87
  88
  89 void *
  90 gc_general_alloc(long bytes, int unboxed_p, int quick_p) {
  91     lispobj *new=new_space_free_pointer;
  92     new_space_free_pointer+=(bytes/N_WORD_BYTES);
  93     return new;
  94 }
  95
  96 lispobj  copy_large_unboxed_object(lispobj object, long nwords) {
  97     return copy_object(object,nwords);
  98 }
  99 lispobj  copy_unboxed_object(lispobj object, long nwords) {
 100     return copy_object(object,nwords);
 101 }
 102 lispobj  copy_large_object(lispobj object, long nwords) {
 103     return copy_object(object,nwords);
 104 }
 105
 106 /* Note: The generic GC interface we're implementing passes us a
 107  * last_generation argument. That's meaningless for us, since we're
 108  * not a generational GC. So we ignore it. */
 109 void
 110 collect_garbage(generation_index_t ignore)
 111 {
 112 #ifdef PRINTNOISE
 113     struct timeval start_tv, stop_tv;
 114     struct rusage start_rusage, stop_rusage;
 115     double real_time, system_time, user_time;
 116     double percent_retained, gc_rate;
 117     unsigned long size_discarded;
 118 #endif
 119     unsigned long size_retained;
 120     lispobj *current_static_space_free_pointer;
 121     unsigned long static_space_size;
 122     unsigned long control_stack_size, binding_stack_size;
 123     sigset_t tmp, old;
 124     struct thread *th=arch_os_get_current_thread();
 125
 126 #ifdef PRINTNOISE
 127     printf("[Collecting garbage ... \n");
 128
 129     getrusage(RUSAGE_SELF, &start_rusage);
 130     gettimeofday(&start_tv, (struct timezone *) 0);
 131 #endif
 132
 133     /* it's possible that signals are blocked already if this was called
 134      * from a signal handler (e.g. with the sigsegv gc_trigger stuff) */
 135     sigemptyset(&tmp);
 136     sigaddset_blockable(&tmp);
 137     thread_sigmask(SIG_BLOCK, &tmp, &old);
 138
 139     current_static_space_free_pointer =
 140         (lispobj *) ((unsigned long)
 141                      SymbolValue(STATIC_SPACE_FREE_POINTER,0));
 142
 143
 144     /* Set up from space and new space pointers. */
 145
 146     from_space = current_dynamic_space;
 147     from_space_free_pointer = dynamic_space_free_pointer;
 148
 149 #ifdef PRINTNOISE
 150     fprintf(stderr,"from_space = %lx\n",
 151             (unsigned long) current_dynamic_space);
 152 #endif
 153     if (current_dynamic_space == (lispobj *) DYNAMIC_0_SPACE_START)
 154         new_space = (lispobj *)DYNAMIC_1_SPACE_START;
 155     else if (current_dynamic_space == (lispobj *) DYNAMIC_1_SPACE_START)
 156         new_space = (lispobj *) DYNAMIC_0_SPACE_START;
 157     else {
 158         lose("GC lossage.  Current dynamic space is bogus!\n");
 159     }
 160     new_space_free_pointer = new_space;
 161
 162     /* Initialize the weak pointer list. */
 163     weak_pointers = (struct weak_pointer *) NULL;
 164
 165
 166     /* Scavenge all of the roots. */
 167 #ifdef PRINTNOISE
 168     printf("Scavenging interrupt contexts ...\n");
 169 #endif
 170     scavenge_interrupt_contexts();
 171
 172 #ifdef PRINTNOISE
 173     printf("Scavenging interrupt handlers (%d bytes) ...\n",
 174            (int)sizeof(interrupt_handlers));
 175 #endif
 176     scavenge((lispobj *) interrupt_handlers,
 177              sizeof(interrupt_handlers) / sizeof(lispobj));
 178
 179     /* _size quantities are in units of sizeof(lispobj) - i.e. 4 */
 180     control_stack_size =
 181         current_control_stack_pointer-
 182         (lispobj *)th->control_stack_start;
 183 #ifdef PRINTNOISE
 184     printf("Scavenging the control stack at %p (%ld words) ...\n",
 185            ((lispobj *)th->control_stack_start),
 186            control_stack_size);
 187 #endif
 188     scavenge(((lispobj *)th->control_stack_start), control_stack_size);
 189
 190
 191     binding_stack_size =
 192         current_binding_stack_pointer -
 193         (lispobj *)th->binding_stack_start;
 194 #ifdef PRINTNOISE
 195     printf("Scavenging the binding stack %x - %x (%d words) ...\n",
 196            th->binding_stack_start,current_binding_stack_pointer,
 197            (int)(binding_stack_size));
 198 #endif
 199     scavenge(((lispobj *)th->binding_stack_start), binding_stack_size);
 200
 201     static_space_size =
 202         current_static_space_free_pointer - (lispobj *) STATIC_SPACE_START;
 203 #ifdef PRINTNOISE
 204     printf("Scavenging static space %x - %x (%d words) ...\n",
 205            STATIC_SPACE_START,current_static_space_free_pointer,
 206            (int)(static_space_size));
 207 #endif
 208     scavenge(((lispobj *)STATIC_SPACE_START), static_space_size);
 209
 210     /* Scavenge newspace. */
 211 #ifdef PRINTNOISE
 212     printf("Scavenging new space (%d bytes) ...\n",
 213            (int)((new_space_free_pointer - new_space) * sizeof(lispobj)));
 214 #endif
 215     scavenge_newspace();
 216
 217
 218 #if defined(DEBUG_PRINT_GARBAGE)
 219     print_garbage(from_space, from_space_free_pointer);
 220 #endif
 221
 222     /* Scan the weak pointers. */
 223 #ifdef PRINTNOISE
 224     printf("Scanning weak hash tables ...\n");
 225 #endif
 226     scan_weak_hash_tables();
 227
 228     /* Scan the weak pointers. */
 229 #ifdef PRINTNOISE
 230     printf("Scanning weak pointers ...\n");
 231 #endif
 232     scan_weak_pointers();
 233
 234     /* Flip spaces. */
 235 #ifdef PRINTNOISE
 236     printf("Flipping spaces ...\n");
 237 #endif
 238
 239     /* Maybe FIXME: it's possible that we could significantly reduce
 240      * RSS by zeroing the from_space or madvise(MADV_DONTNEED) or
 241      * similar os-dependent tricks here */
 242     os_zero((os_vm_address_t) from_space,
 243             (os_vm_size_t) dynamic_space_size);
 244
 245     current_dynamic_space = new_space;
 246     dynamic_space_free_pointer = new_space_free_pointer;
 247
 248 #ifdef PRINTNOISE
 249     size_discarded = (from_space_free_pointer - from_space) * sizeof(lispobj);
 250 #endif
 251     size_retained = (new_space_free_pointer - new_space) * sizeof(lispobj);
 252
 253     os_flush_icache((os_vm_address_t)new_space, size_retained);
 254
 255     /* Zero stack. */
 256 #ifdef PRINTNOISE
 257     printf("Zeroing empty part of control stack ...\n");
 258 #endif
 259     zero_stack();
 260     set_auto_gc_trigger(size_retained+bytes_consed_between_gcs);
 261     thread_sigmask(SIG_SETMASK, &old, 0);
 262
 263
 264 #ifdef PRINTNOISE
 265     gettimeofday(&stop_tv, (struct timezone *) 0);
 266     getrusage(RUSAGE_SELF, &stop_rusage);
 267
 268     printf("done.]\n");
 269
 270     percent_retained = (((float) size_retained) /
 271                         ((float) size_discarded)) * 100.0;
 272
 273     printf("Total of %ld bytes out of %ld bytes retained (%3.2f%%).\n",
 274            size_retained, size_discarded, percent_retained);
 275
 276     real_time = tv_diff(&stop_tv, &start_tv);
 277     user_time = tv_diff(&stop_rusage.ru_utime, &start_rusage.ru_utime);
 278     system_time = tv_diff(&stop_rusage.ru_stime, &start_rusage.ru_stime);
 279
 280     printf("Statistics: %10.2fs real, %10.2fs user, %10.2fs system.\n",
 281            real_time, user_time, system_time);
 282
 283     gc_rate = ((float) size_retained / (float) (1<<20)) / real_time;
 284
 285     printf("%10.2f M bytes/sec collected.\n", gc_rate);
 286 #endif
 287 }
 288
 289 \f
 290 /* scavenging */
 291
 292 static void
 293 scavenge_newspace(void)
 294 {
 295     lispobj *here, *next;
 296
 297     here = new_space;
 298     while (here < new_space_free_pointer) {
 299         /*      printf("here=%lx, new_space_free_pointer=%lx\n",
 300                 here,new_space_free_pointer); */
 301         next = new_space_free_pointer;
 302         scavenge(here, next - here);
 303         scav_weak_hash_tables();
 304         here = next;
 305     }
 306     /* printf("done with newspace\n"); */
 307 }
 308 \f
 309 /* scavenging interrupt contexts */
 310
 311 static int boxed_registers[] = BOXED_REGISTERS;
 312
 313 static void
 314 scavenge_interrupt_context(os_context_t *context)
 315 {
 316     int i;
 317 #ifdef reg_LIP
 318     unsigned long lip;
 319     unsigned long lip_offset;
 320     int lip_register_pair;
 321 #endif
 322     unsigned long pc_code_offset;
 323 #ifdef ARCH_HAS_LINK_REGISTER
 324     unsigned long lr_code_offset;
 325 #endif
 326 #ifdef ARCH_HAS_NPC_REGISTER
 327     unsigned long npc_code_offset;
 328 #endif
 329 #ifdef DEBUG_SCAVENGE_VERBOSE
 330     fprintf(stderr, "Scavenging interrupt context at 0x%x\n",context);
 331 #endif
 332     /* Find the LIP's register pair and calculate its offset */
 333     /* before we scavenge the context. */
 334 #ifdef reg_LIP
 335     lip = *os_context_register_addr(context, reg_LIP);
 336     /* 0x7FFFFFFF on 32-bit platforms;
 337        0x7FFFFFFFFFFFFFFF on 64-bit platforms */
 338     lip_offset = (((unsigned long)1) << (N_WORD_BITS - 1)) - 1;
 339     lip_register_pair = -1;
 340     for (i = 0; i < (int)(sizeof(boxed_registers) / sizeof(int)); i++) {
 341         unsigned long reg;
 342         unsigned long offset;
 343         int index;
 344
 345         index = boxed_registers[i];
 346         reg = *os_context_register_addr(context, index);
 347         /* would be using PTR if not for integer length issues */
 348         if ((reg & ~((1L<<N_LOWTAG_BITS)-1)) <= lip) {
 349             offset = lip - reg;
 350             if (offset < lip_offset) {
 351                 lip_offset = offset;
 352                 lip_register_pair = index;
 353             }
 354         }
 355     }
 356 #endif /* reg_LIP */
 357
 358     /* Compute the PC's offset from the start of the CODE */
 359     /* register. */
 360     pc_code_offset =
 361         *os_context_pc_addr(context) -
 362         *os_context_register_addr(context, reg_CODE);
 363 #ifdef ARCH_HAS_NPC_REGISTER
 364     npc_code_offset =
 365         *os_context_npc_addr(context) -
 366         *os_context_register_addr(context, reg_CODE);
 367 #endif
 368 #ifdef ARCH_HAS_LINK_REGISTER
 369     lr_code_offset =
 370         *os_context_lr_addr(context) -
 371         *os_context_register_addr(context, reg_CODE);
 372 #endif
 373
 374     /* Scavenge all boxed registers in the context. */
 375     for (i = 0; i < (int)(sizeof(boxed_registers) / sizeof(int)); i++) {
 376         int index;
 377         lispobj foo;
 378
 379         index = boxed_registers[i];
 380         foo = *os_context_register_addr(context,index);
 381         scavenge((lispobj *) &foo, 1);
 382         *os_context_register_addr(context,index) = foo;
 383
 384         /* this is unlikely to work as intended on bigendian
 385          * 64 bit platforms */
 386
 387         scavenge((lispobj *)
 388                  os_context_register_addr(context, index), 1);
 389     }
 390
 391 #ifdef reg_LIP
 392     /* Fix the LIP */
 393     *os_context_register_addr(context, reg_LIP) =
 394         *os_context_register_addr(context, lip_register_pair) + lip_offset;
 395 #endif /* reg_LIP */
 396
 397     /* Fix the PC if it was in from space */
 398     if (from_space_p(*os_context_pc_addr(context)))
 399         *os_context_pc_addr(context) =
 400             *os_context_register_addr(context, reg_CODE) + pc_code_offset;
 401 #ifdef ARCH_HAS_LINK_REGISTER
 402     /* Fix the LR ditto; important if we're being called from
 403      * an assembly routine that expects to return using blr, otherwise
 404      * harmless */
 405     if (from_space_p(*os_context_lr_addr(context)))
 406         *os_context_lr_addr(context) =
 407             *os_context_register_addr(context, reg_CODE) + lr_code_offset;
 408 #endif
 409
 410 #ifdef ARCH_HAS_NPC_REGISTER
 411     if (from_space_p(*os_context_npc_addr(context)))
 412         *os_context_npc_addr(context) =
 413             *os_context_register_addr(context, reg_CODE) + npc_code_offset;
 414 #endif
 415 }
 416
 417 void scavenge_interrupt_contexts(void)
 418 {
 419     int i, index;
 420     os_context_t *context;
 421
 422     struct thread *th=arch_os_get_current_thread();
 423
 424     index = fixnum_value(SymbolValue(FREE_INTERRUPT_CONTEXT_INDEX,0));
 425
 426
 427 #ifdef DEBUG_SCAVENGE_VERBOSE
 428     fprintf(stderr, "%d interrupt contexts to scan\n",index);
 429 #endif
 430     for (i = 0; i < index; i++) {
 431         context = th->interrupt_contexts[i];
 432         scavenge_interrupt_context(context);
 433     }
 434 }
 435
 436 \f
 437 /* debugging code */
 438
 439 void
 440 print_garbage(lispobj *from_space, lispobj *from_space_free_pointer)
 441 {
 442     lispobj *start;
 443     int total_words_not_copied;
 444
 445     printf("Scanning from space ...\n");
 446
 447     total_words_not_copied = 0;
 448     start = from_space;
 449     while (start < from_space_free_pointer) {
 450         lispobj object;
 451         int forwardp, type, nwords;
 452         lispobj header;
 453
 454         object = *start;
 455         forwardp = is_lisp_pointer(object) && new_space_p(object);
 456
 457         if (forwardp) {
 458             int tag;
 459             lispobj *pointer;
 460
 461             tag = lowtag_of(object);
 462
 463             switch (tag) {
 464             case LIST_POINTER_LOWTAG:
 465                 nwords = 2;
 466                 break;
 467             case INSTANCE_POINTER_LOWTAG:
 468                 printf("Don't know about instances yet!\n");
 469                 nwords = 1;
 470                 break;
 471             case FUN_POINTER_LOWTAG:
 472                 nwords = 1;
 473                 break;
 474             case OTHER_POINTER_LOWTAG:
 475                 pointer = (lispobj *) native_pointer(object);
 476                 header = *pointer;
 477                 type = widetag_of(header);
 478                 nwords = (sizetab[type])(pointer);
 479                 break;
 480             default: nwords=1;  /* shut yer whinging, gcc */
 481             }
 482         } else {
 483             type = widetag_of(object);
 484             nwords = (sizetab[type])(start);
 485             total_words_not_copied += nwords;
 486             printf("%4d words not copied at 0x%16lx; ",
 487                    nwords, (unsigned long) start);
 488             printf("Header word is 0x%08x\n",
 489                    (unsigned int) object);
 490         }
 491         start += nwords;
 492     }
 493     printf("%d total words not copied.\n", total_words_not_copied);
 494 }
 495
 496 \f
 497 /* weak pointers */
 498
 499 #define WEAK_POINTER_NWORDS \
 500         CEILING((sizeof(struct weak_pointer) / sizeof(lispobj)), 2)
 501
 502 static long
 503 scav_weak_pointer(lispobj *where, lispobj object)
 504 {
 505     /* Do not let GC scavenge the value slot of the weak pointer */
 506     /* (that is why it is a weak pointer).  Note:  we could use */
 507     /* the scav_unboxed method here. */
 508
 509     return WEAK_POINTER_NWORDS;
 510 }
 511 \f
 512 lispobj *
 513 search_read_only_space(void *pointer)
 514 {
 515     lispobj* start = (lispobj*)READ_ONLY_SPACE_START;
 516     lispobj* end = (lispobj*)SymbolValue(READ_ONLY_SPACE_FREE_POINTER,0);
 517     if ((pointer < (void *)start) || (pointer >= (void *)end))
 518         return NULL;
 519     return (gc_search_space(start,
 520                             (((lispobj *)pointer)+2)-start,
 521                             (lispobj *)pointer));
 522 }
 523
 524 lispobj *
 525 search_static_space(void *pointer)
 526 {
 527     lispobj* start = (lispobj*)STATIC_SPACE_START;
 528     lispobj* end = (lispobj*)SymbolValue(STATIC_SPACE_FREE_POINTER,0);
 529     if ((pointer < (void *)start) || (pointer >= (void *)end))
 530         return NULL;
 531     return (gc_search_space(start,
 532                             (((lispobj *)pointer)+2)-start,
 533                             (lispobj *)pointer));
 534 }
 535
 536 lispobj *
 537 search_dynamic_space(void *pointer)
 538 {
 539     lispobj *start = (lispobj *) current_dynamic_space;
 540     lispobj *end = (lispobj *) dynamic_space_free_pointer;
 541     if ((pointer < (void *)start) || (pointer >= (void *)end))
 542         return NULL;
 543     return (gc_search_space(start,
 544                             (((lispobj *)pointer)+2)-start,
 545                             (lispobj *)pointer));
 546 }
 547 \f
 548 /* initialization.  if gc_init can be moved to after core load, we could
 549  * combine these two functions */
 550
 551 void
 552 gc_init(void)
 553 {
 554     gc_init_tables();
 555     scavtab[WEAK_POINTER_WIDETAG] = scav_weak_pointer;
 556 }
 557
 558 void
 559 gc_initialize_pointers(void)
 560 {
 561     /* FIXME: We do nothing here.  We (briefly) misguidedly attempted
 562        to set current_dynamic_space to DYNAMIC_0_SPACE_START here,
 563        forgetting that (a) actually it could be the other and (b) it's
 564        set in coreparse.c anyway.  There's a FIXME note left here to
 565        note that current_dynamic_space is a violation of OAOO: we can
 566        tell which dynamic space we're currently in by looking at
 567        dynamic_space_free_pointer.  -- CSR, 2002-08-09 */
 568 }
 569
 570
 571
 572 \f
 573 /* noise to manipulate the gc trigger stuff */
 574
 575 /* Functions that substantially change the dynamic space free pointer
 576  * (collect_garbage, purify) are responsible also for resetting the
 577  * auto_gc_trigger */
 578 void set_auto_gc_trigger(os_vm_size_t dynamic_usage)
 579 {
 580     os_vm_address_t addr;
 581     os_vm_size_t length;
 582
 583     addr = os_round_up_to_page((os_vm_address_t)current_dynamic_space
 584                                + dynamic_usage);
 585     if (addr < (os_vm_address_t)dynamic_space_free_pointer)
 586         lose("set_auto_gc_trigger: tried to set gc trigger too low! (%ld < 0x%08lx)\n",
 587              (unsigned long)dynamic_usage,
 588              (unsigned long)((os_vm_address_t)dynamic_space_free_pointer
 589                              - (os_vm_address_t)current_dynamic_space));
 590
 591     length = os_trunc_size_to_page(dynamic_space_size - dynamic_usage);
 592     if (length < 0)
 593         lose("set_auto_gc_trigger: tried to set gc trigger too high! (0x%08lx)\n",
 594              (unsigned long)dynamic_usage);
 595
 596 #if defined(SUNOS) || defined(SOLARIS)
 597     os_invalidate(addr, length);
 598 #else
 599     os_protect(addr, length, 0);
 600 #endif
 601
 602     current_auto_gc_trigger = (lispobj *)addr;
 603 }
 604
 605 void clear_auto_gc_trigger(void)
 606 {
 607     os_vm_address_t addr;
 608     os_vm_size_t length;
 609
 610     if (current_auto_gc_trigger == NULL)
 611         return;
 612
 613     addr = (os_vm_address_t)current_auto_gc_trigger;
 614     length = dynamic_space_size + (os_vm_address_t)current_dynamic_space - addr;
 615
 616 #if defined(SUNOS) || defined(SOLARIS)
 617     /* don't want to force whole space into swapping mode... */
 618     os_validate(addr, length);
 619 #else
 620     os_protect(addr, length, OS_VM_PROT_ALL);
 621 #endif
 622
 623     current_auto_gc_trigger = NULL;
 624 }
 625
 626 static boolean
 627 gc_trigger_hit(void *addr)
 628 {
 629     if (current_auto_gc_trigger == NULL)
 630         return 0;
 631     else{
 632         return (addr >= (void *)current_auto_gc_trigger &&
 633                 addr <((void *)current_dynamic_space + dynamic_space_size));
 634     }
 635 }
 636
 637 boolean
 638 cheneygc_handle_wp_violation(os_context_t *context, void *addr)
 639 {
 640     if(!foreign_function_call_active && gc_trigger_hit(addr)){
 641         struct thread *thread=arch_os_get_current_thread();
 642         clear_auto_gc_trigger();
 643         /* Don't flood the system with interrupts if the need to gc is
 644          * already noted. This can happen for example when SUB-GC
 645          * allocates or after a gc triggered in a WITHOUT-GCING. */
 646         if (SymbolValue(GC_PENDING,thread) == NIL) {
 647             if (SymbolValue(GC_INHIBIT,thread) == NIL) {
 648                 if (arch_pseudo_atomic_atomic(context)) {
 649                     /* set things up so that GC happens when we finish
 650                      * the PA section */
 651                     SetSymbolValue(GC_PENDING,T,thread);
 652                     arch_set_pseudo_atomic_interrupted(context);
 653                 } else {
 654                     maybe_gc(context);
 655                 }
 656             } else {
 657                 SetSymbolValue(GC_PENDING,T,thread);
 658             }
 659         }
 660         return 1;
 661     }
 662     return 0;
 663 }