1 /*- 2 * Copyright (c) 2005-2007, Joseph Koshy 3 * Copyright (c) 2007 The FreeBSD Foundation 4 * All rights reserved. 5 * 6 * Portions of this software were developed by A. Joseph Koshy under 7 * sponsorship from the FreeBSD Foundation and Google, Inc. 8 * 9 * Redistribution and use in source and binary forms, with or without 10 * modification, are permitted provided that the following conditions 11 * are met: 12 * 1. Redistributions of source code must retain the above copyright 13 * notice, this list of conditions and the following disclaimer. 14 * 2. Redistributions in binary form must reproduce the above copyright 15 * notice, this list of conditions and the following disclaimer in the 16 * documentation and/or other materials provided with the distribution. 17 * 18 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 19 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 20 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 21 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 22 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 23 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 24 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 25 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 26 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 27 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 28 * SUCH DAMAGE. 29 */ 30 31 /* 32 * Transform a hwpmc(4) log into human readable form, and into 33 * gprof(1) compatible profiles. 34 */ 35 36 #include <sys/cdefs.h> 37 __FBSDID("$FreeBSD$"); 38 39 #include <sys/param.h> 40 #include <sys/endian.h> 41 #include <sys/gmon.h> 42 #include <sys/imgact_aout.h> 43 #include <sys/imgact_elf.h> 44 #include <sys/mman.h> 45 #include <sys/pmc.h> 46 #include <sys/queue.h> 47 #include <sys/socket.h> 48 #include <sys/stat.h> 49 #include <sys/wait.h> 50 51 #include <netinet/in.h> 52 53 #include <assert.h> 54 #include <curses.h> 55 #include <err.h> 56 #include <errno.h> 57 #include <fcntl.h> 58 #include <gelf.h> 59 #include <libgen.h> 60 #include <limits.h> 61 #include <netdb.h> 62 #include <pmc.h> 63 #include <pmclog.h> 64 #include <sysexits.h> 65 #include <stdint.h> 66 #include <stdio.h> 67 #include <stdlib.h> 68 #include <string.h> 69 #include <unistd.h> 70 71 #include "pmcstat.h" 72 #include "pmcstat_log.h" 73 #include "pmcstat_top.h" 74 #include "pmcpl_callgraph.h" 75 76 /* Get the sample value in percent related to nsamples. */ 77 #define PMCPL_CG_COUNTP(a) \ 78 ((a)->pcg_count * 100.0 / nsamples) 79 80 /* 81 * The toplevel CG nodes (i.e., with rank == 0) are placed in a hash table. 82 */ 83 84 struct pmcstat_cgnode_hash_list pmcstat_cgnode_hash[PMCSTAT_NHASH]; 85 int pmcstat_cgnode_hash_count; 86 87 static pmcstat_interned_string pmcstat_previous_filename_printed; 88 89 static struct pmcstat_cgnode * 90 pmcstat_cgnode_allocate(struct pmcstat_image *image, uintfptr_t pc) 91 { 92 struct pmcstat_cgnode *cg; 93 94 if ((cg = malloc(sizeof(*cg))) == NULL) 95 err(EX_OSERR, "ERROR: Cannot allocate callgraph node"); 96 97 cg->pcg_image = image; 98 cg->pcg_func = pc; 99 100 cg->pcg_count = 0; 101 cg->pcg_nchildren = 0; 102 LIST_INIT(&cg->pcg_children); 103 104 return (cg); 105 } 106 107 /* 108 * Free a node and its children. 109 */ 110 static void 111 pmcstat_cgnode_free(struct pmcstat_cgnode *cg) 112 { 113 struct pmcstat_cgnode *cgc, *cgtmp; 114 115 LIST_FOREACH_SAFE(cgc, &cg->pcg_children, pcg_sibling, cgtmp) 116 pmcstat_cgnode_free(cgc); 117 free(cg); 118 } 119 120 /* 121 * Look for a callgraph node associated with pmc `pmcid' in the global 122 * hash table that corresponds to the given `pc' value in the process 123 * `pp'. 124 */ 125 static struct pmcstat_cgnode * 126 pmcstat_cgnode_hash_lookup_pc(struct pmcstat_process *pp, pmc_id_t pmcid, 127 uintfptr_t pc, int usermode) 128 { 129 struct pmcstat_pcmap *ppm; 130 struct pmcstat_symbol *sym; 131 struct pmcstat_image *image; 132 struct pmcstat_cgnode *cg; 133 struct pmcstat_cgnode_hash *h; 134 uintfptr_t loadaddress; 135 unsigned int i, hash; 136 137 ppm = pmcstat_process_find_map(usermode ? pp : pmcstat_kernproc, pc); 138 if (ppm == NULL) 139 return (NULL); 140 141 image = ppm->ppm_image; 142 143 loadaddress = ppm->ppm_lowpc + image->pi_vaddr - image->pi_start; 144 pc -= loadaddress; /* Convert to an offset in the image. */ 145 146 /* 147 * Try determine the function at this offset. If we can't 148 * find a function round leave the `pc' value alone. 149 */ 150 if ((sym = pmcstat_symbol_search(image, pc)) != NULL) 151 pc = sym->ps_start; 152 153 for (hash = i = 0; i < sizeof(uintfptr_t); i++) 154 hash += (pc >> i) & 0xFF; 155 156 hash &= PMCSTAT_HASH_MASK; 157 158 cg = NULL; 159 LIST_FOREACH(h, &pmcstat_cgnode_hash[hash], pch_next) 160 { 161 if (h->pch_pmcid != pmcid) 162 continue; 163 164 cg = h->pch_cgnode; 165 166 assert(cg != NULL); 167 168 if (cg->pcg_image == image && cg->pcg_func == pc) 169 return (cg); 170 } 171 172 /* 173 * We haven't seen this (pmcid, pc) tuple yet, so allocate a 174 * new callgraph node and a new hash table entry for it. 175 */ 176 cg = pmcstat_cgnode_allocate(image, pc); 177 if ((h = malloc(sizeof(*h))) == NULL) 178 err(EX_OSERR, "ERROR: Could not allocate callgraph node"); 179 180 h->pch_pmcid = pmcid; 181 h->pch_cgnode = cg; 182 LIST_INSERT_HEAD(&pmcstat_cgnode_hash[hash], h, pch_next); 183 184 pmcstat_cgnode_hash_count++; 185 186 return (cg); 187 } 188 189 /* 190 * Compare two callgraph nodes for sorting. 191 */ 192 static int 193 pmcstat_cgnode_compare(const void *a, const void *b) 194 { 195 const struct pmcstat_cgnode *const *pcg1, *const *pcg2, *cg1, *cg2; 196 197 pcg1 = (const struct pmcstat_cgnode *const *) a; 198 cg1 = *pcg1; 199 pcg2 = (const struct pmcstat_cgnode *const *) b; 200 cg2 = *pcg2; 201 202 /* Sort in reverse order */ 203 if (cg1->pcg_count < cg2->pcg_count) 204 return (1); 205 if (cg1->pcg_count > cg2->pcg_count) 206 return (-1); 207 return (0); 208 } 209 210 /* 211 * Find (allocating if a needed) a callgraph node in the given 212 * parent with the same (image, pcoffset) pair. 213 */ 214 215 static struct pmcstat_cgnode * 216 pmcstat_cgnode_find(struct pmcstat_cgnode *parent, struct pmcstat_image *image, 217 uintfptr_t pcoffset) 218 { 219 struct pmcstat_cgnode *child; 220 221 LIST_FOREACH(child, &parent->pcg_children, pcg_sibling) { 222 if (child->pcg_image == image && 223 child->pcg_func == pcoffset) 224 return (child); 225 } 226 227 /* 228 * Allocate a new structure. 229 */ 230 231 child = pmcstat_cgnode_allocate(image, pcoffset); 232 233 /* 234 * Link it into the parent. 235 */ 236 LIST_INSERT_HEAD(&parent->pcg_children, child, pcg_sibling); 237 parent->pcg_nchildren++; 238 239 return (child); 240 } 241 242 /* 243 * Print one callgraph node. The output format is: 244 * 245 * indentation %(parent's samples) #nsamples function@object 246 */ 247 static void 248 pmcstat_cgnode_print(struct pmcstat_cgnode *cg, int depth, uint32_t total) 249 { 250 uint32_t n; 251 const char *space; 252 struct pmcstat_symbol *sym; 253 struct pmcstat_cgnode **sortbuffer, **cgn, *pcg; 254 255 space = " "; 256 257 if (depth > 0) 258 (void) fprintf(args.pa_graphfile, "%*s", depth, space); 259 260 if (cg->pcg_count == total) 261 (void) fprintf(args.pa_graphfile, "100.0%% "); 262 else 263 (void) fprintf(args.pa_graphfile, "%05.2f%% ", 264 100.0 * cg->pcg_count / total); 265 266 n = fprintf(args.pa_graphfile, " [%u] ", cg->pcg_count); 267 268 /* #samples is a 12 character wide field. */ 269 if (n < 12) 270 (void) fprintf(args.pa_graphfile, "%*s", 12 - n, space); 271 272 if (depth > 0) 273 (void) fprintf(args.pa_graphfile, "%*s", depth, space); 274 275 sym = pmcstat_symbol_search(cg->pcg_image, cg->pcg_func); 276 if (sym) 277 (void) fprintf(args.pa_graphfile, "%s", 278 pmcstat_string_unintern(sym->ps_name)); 279 else 280 (void) fprintf(args.pa_graphfile, "%p", 281 (void *) (cg->pcg_image->pi_vaddr + cg->pcg_func)); 282 283 if (pmcstat_previous_filename_printed != 284 cg->pcg_image->pi_fullpath) { 285 pmcstat_previous_filename_printed = cg->pcg_image->pi_fullpath; 286 (void) fprintf(args.pa_graphfile, " @ %s\n", 287 pmcstat_string_unintern( 288 pmcstat_previous_filename_printed)); 289 } else 290 (void) fprintf(args.pa_graphfile, "\n"); 291 292 if (cg->pcg_nchildren == 0) 293 return; 294 295 if ((sortbuffer = (struct pmcstat_cgnode **) 296 malloc(sizeof(struct pmcstat_cgnode *) * 297 cg->pcg_nchildren)) == NULL) 298 err(EX_OSERR, "ERROR: Cannot print callgraph"); 299 cgn = sortbuffer; 300 301 LIST_FOREACH(pcg, &cg->pcg_children, pcg_sibling) 302 *cgn++ = pcg; 303 304 assert(cgn - sortbuffer == (int) cg->pcg_nchildren); 305 306 qsort(sortbuffer, cg->pcg_nchildren, sizeof(struct pmcstat_cgnode *), 307 pmcstat_cgnode_compare); 308 309 for (cgn = sortbuffer, n = 0; n < cg->pcg_nchildren; n++, cgn++) 310 pmcstat_cgnode_print(*cgn, depth+1, cg->pcg_count); 311 312 free(sortbuffer); 313 } 314 315 /* 316 * Record a callchain. 317 */ 318 319 void 320 pmcpl_cg_process(struct pmcstat_process *pp, struct pmcstat_pmcrecord *pmcr, 321 uint32_t nsamples, uintfptr_t *cc, int usermode, uint32_t cpu) 322 { 323 uintfptr_t pc, loadaddress; 324 uint32_t n; 325 struct pmcstat_image *image; 326 struct pmcstat_pcmap *ppm; 327 struct pmcstat_symbol *sym; 328 struct pmcstat_cgnode *parent, *child; 329 struct pmcstat_process *km; 330 pmc_id_t pmcid; 331 332 (void) cpu; 333 334 /* 335 * Find the callgraph node recorded in the global hash table 336 * for this (pmcid, pc). 337 */ 338 339 pc = cc[0]; 340 pmcid = pmcr->pr_pmcid; 341 parent = pmcstat_cgnode_hash_lookup_pc(pp, pmcid, pc, usermode); 342 if (parent == NULL) { 343 pmcstat_stats.ps_callchain_dubious_frames++; 344 pmcr->pr_dubious_frames++; 345 return; 346 } 347 348 parent->pcg_count++; 349 350 /* 351 * For each return address in the call chain record, subject 352 * to the maximum depth desired. 353 * - Find the image associated with the sample. Stop if there 354 * there is no valid image at that address. 355 * - Find the function that overlaps the return address. 356 * - If found: use the start address of the function. 357 * If not found (say an object's symbol table is not present or 358 * is incomplete), round down to th gprof bucket granularity. 359 * - Convert return virtual address to an offset in the image. 360 * - Look for a child with the same {offset,image} tuple, 361 * inserting one if needed. 362 * - Increment the count of occurrences of the child. 363 */ 364 km = pmcstat_kernproc; 365 366 for (n = 1; n < (uint32_t) args.pa_graphdepth && n < nsamples; n++, 367 parent = child) { 368 pc = cc[n]; 369 370 ppm = pmcstat_process_find_map(usermode ? pp : km, pc); 371 if (ppm == NULL) { 372 /* Detect full frame capture (kernel + user). */ 373 if (!usermode) { 374 ppm = pmcstat_process_find_map(pp, pc); 375 if (ppm != NULL) 376 km = pp; 377 } 378 } 379 if (ppm == NULL) 380 return; 381 382 image = ppm->ppm_image; 383 loadaddress = ppm->ppm_lowpc + image->pi_vaddr - 384 image->pi_start; 385 pc -= loadaddress; 386 387 if ((sym = pmcstat_symbol_search(image, pc)) != NULL) 388 pc = sym->ps_start; 389 390 child = pmcstat_cgnode_find(parent, image, pc); 391 child->pcg_count++; 392 } 393 } 394 395 /* 396 * Printing a callgraph for a PMC. 397 */ 398 static void 399 pmcstat_callgraph_print_for_pmcid(struct pmcstat_pmcrecord *pmcr) 400 { 401 int n, nentries; 402 uint32_t nsamples; 403 pmc_id_t pmcid; 404 struct pmcstat_cgnode **sortbuffer, **cgn; 405 struct pmcstat_cgnode_hash *pch; 406 407 /* 408 * We pull out all callgraph nodes in the top-level hash table 409 * with a matching PMC id. We then sort these based on the 410 * frequency of occurrence. Each callgraph node is then 411 * printed. 412 */ 413 414 nsamples = 0; 415 pmcid = pmcr->pr_pmcid; 416 if ((sortbuffer = (struct pmcstat_cgnode **) 417 malloc(sizeof(struct pmcstat_cgnode *) * 418 pmcstat_cgnode_hash_count)) == NULL) 419 err(EX_OSERR, "ERROR: Cannot sort callgraph"); 420 cgn = sortbuffer; 421 422 for (n = 0; n < PMCSTAT_NHASH; n++) 423 LIST_FOREACH(pch, &pmcstat_cgnode_hash[n], pch_next) 424 if (pch->pch_pmcid == pmcid) { 425 nsamples += pch->pch_cgnode->pcg_count; 426 *cgn++ = pch->pch_cgnode; 427 } 428 429 nentries = cgn - sortbuffer; 430 assert(nentries <= pmcstat_cgnode_hash_count); 431 432 if (nentries == 0) { 433 free(sortbuffer); 434 return; 435 } 436 437 qsort(sortbuffer, nentries, sizeof(struct pmcstat_cgnode *), 438 pmcstat_cgnode_compare); 439 440 (void) fprintf(args.pa_graphfile, 441 "@ %s [%u samples]\n\n", 442 pmcstat_string_unintern(pmcr->pr_pmcname), 443 nsamples); 444 445 for (cgn = sortbuffer, n = 0; n < nentries; n++, cgn++) { 446 pmcstat_previous_filename_printed = NULL; 447 pmcstat_cgnode_print(*cgn, 0, nsamples); 448 (void) fprintf(args.pa_graphfile, "\n"); 449 } 450 451 free(sortbuffer); 452 } 453 454 /* 455 * Print out callgraphs. 456 */ 457 458 static void 459 pmcstat_callgraph_print(void) 460 { 461 struct pmcstat_pmcrecord *pmcr; 462 463 LIST_FOREACH(pmcr, &pmcstat_pmcs, pr_next) 464 pmcstat_callgraph_print_for_pmcid(pmcr); 465 } 466 467 static void 468 pmcstat_cgnode_topprint(struct pmcstat_cgnode *cg, 469 int depth, uint32_t nsamples) 470 { 471 int v_attrs, vs_len, ns_len, width, len, n, nchildren; 472 float v; 473 char ns[30], vs[10]; 474 struct pmcstat_symbol *sym; 475 struct pmcstat_cgnode **sortbuffer, **cgn, *pcg; 476 477 (void) depth; 478 479 /* Format value. */ 480 v = PMCPL_CG_COUNTP(cg); 481 snprintf(vs, sizeof(vs), "%.1f", v); 482 v_attrs = PMCSTAT_ATTRPERCENT(v); 483 484 /* Format name. */ 485 sym = pmcstat_symbol_search(cg->pcg_image, cg->pcg_func); 486 if (sym != NULL) { 487 snprintf(ns, sizeof(ns), "%s", 488 pmcstat_string_unintern(sym->ps_name)); 489 } else 490 snprintf(ns, sizeof(ns), "%p", 491 (void *)cg->pcg_func); 492 493 PMCSTAT_ATTRON(v_attrs); 494 PMCSTAT_PRINTW("%5.5s", vs); 495 PMCSTAT_ATTROFF(v_attrs); 496 PMCSTAT_PRINTW(" %-10.10s %-20.20s", 497 pmcstat_string_unintern(cg->pcg_image->pi_name), 498 ns); 499 500 nchildren = cg->pcg_nchildren; 501 if (nchildren == 0) { 502 PMCSTAT_PRINTW("\n"); 503 return; 504 } 505 506 width = pmcstat_displaywidth - 40; 507 508 if ((sortbuffer = (struct pmcstat_cgnode **) 509 malloc(sizeof(struct pmcstat_cgnode *) * 510 nchildren)) == NULL) 511 err(EX_OSERR, "ERROR: Cannot print callgraph"); 512 cgn = sortbuffer; 513 514 LIST_FOREACH(pcg, &cg->pcg_children, pcg_sibling) 515 *cgn++ = pcg; 516 517 assert(cgn - sortbuffer == (int)nchildren); 518 519 qsort(sortbuffer, nchildren, sizeof(struct pmcstat_cgnode *), 520 pmcstat_cgnode_compare); 521 522 /* Count how many callers. */ 523 for (cgn = sortbuffer, n = 0; n < nchildren; n++, cgn++) { 524 pcg = *cgn; 525 526 v = PMCPL_CG_COUNTP(pcg); 527 if (v < pmcstat_threshold) 528 break; 529 } 530 nchildren = n; 531 532 for (cgn = sortbuffer, n = 0; n < nchildren; n++, cgn++) { 533 pcg = *cgn; 534 535 /* Format value. */ 536 if (nchildren > 1) { 537 v = PMCPL_CG_COUNTP(pcg); 538 vs_len = snprintf(vs, sizeof(vs), ":%.1f", v); 539 v_attrs = PMCSTAT_ATTRPERCENT(v); 540 } else 541 vs_len = 0; 542 543 /* Format name. */ 544 sym = pmcstat_symbol_search(pcg->pcg_image, pcg->pcg_func); 545 if (sym != NULL) { 546 ns_len = snprintf(ns, sizeof(ns), "%s", 547 pmcstat_string_unintern(sym->ps_name)); 548 } else 549 ns_len = snprintf(ns, sizeof(ns), "%p", 550 (void *)pcg->pcg_func); 551 552 len = ns_len + vs_len + 1; 553 if (width - len < 0) { 554 PMCSTAT_PRINTW(" ..."); 555 break; 556 } 557 width -= len; 558 559 PMCSTAT_PRINTW(" %s", ns); 560 if (nchildren > 1) { 561 PMCSTAT_ATTRON(v_attrs); 562 PMCSTAT_PRINTW("%s", vs); 563 PMCSTAT_ATTROFF(v_attrs); 564 } 565 } 566 PMCSTAT_PRINTW("\n"); 567 free(sortbuffer); 568 } 569 570 /* 571 * Top mode display. 572 */ 573 574 void 575 pmcpl_cg_topdisplay(void) 576 { 577 int n, nentries; 578 uint32_t nsamples; 579 struct pmcstat_cgnode **sortbuffer, **cgn; 580 struct pmcstat_cgnode_hash *pch; 581 struct pmcstat_pmcrecord *pmcr; 582 583 pmcr = pmcstat_pmcindex_to_pmcr(pmcstat_pmcinfilter); 584 if (!pmcr) 585 err(EX_SOFTWARE, "ERROR: invalid pmcindex"); 586 587 /* 588 * We pull out all callgraph nodes in the top-level hash table 589 * with a matching PMC index. We then sort these based on the 590 * frequency of occurrence. Each callgraph node is then 591 * printed. 592 */ 593 594 nsamples = 0; 595 596 if ((sortbuffer = (struct pmcstat_cgnode **) 597 malloc(sizeof(struct pmcstat_cgnode *) * 598 pmcstat_cgnode_hash_count)) == NULL) 599 err(EX_OSERR, "ERROR: Cannot sort callgraph"); 600 cgn = sortbuffer; 601 602 for (n = 0; n < PMCSTAT_NHASH; n++) 603 LIST_FOREACH(pch, &pmcstat_cgnode_hash[n], pch_next) 604 if (pmcr == NULL || pch->pch_pmcid == pmcr->pr_pmcid) { 605 nsamples += pch->pch_cgnode->pcg_count; 606 *cgn++ = pch->pch_cgnode; 607 } 608 609 nentries = cgn - sortbuffer; 610 assert(nentries <= pmcstat_cgnode_hash_count); 611 612 if (nentries == 0) { 613 free(sortbuffer); 614 return; 615 } 616 617 qsort(sortbuffer, nentries, sizeof(struct pmcstat_cgnode *), 618 pmcstat_cgnode_compare); 619 620 PMCSTAT_PRINTW("%5.5s %-10.10s %-20.20s %s\n", 621 "%SAMP", "IMAGE", "FUNCTION", "CALLERS"); 622 623 nentries = min(pmcstat_displayheight - 2, nentries); 624 625 for (cgn = sortbuffer, n = 0; n < nentries; n++, cgn++) { 626 if (PMCPL_CG_COUNTP(*cgn) < pmcstat_threshold) 627 break; 628 pmcstat_cgnode_topprint(*cgn, 0, nsamples); 629 } 630 631 free(sortbuffer); 632 } 633 634 /* 635 * Handle top mode keypress. 636 */ 637 638 int 639 pmcpl_cg_topkeypress(int c, WINDOW *w) 640 { 641 642 (void) c; (void) w; 643 644 return 0; 645 } 646 647 int 648 pmcpl_cg_init(void) 649 { 650 int i; 651 652 pmcstat_cgnode_hash_count = 0; 653 pmcstat_previous_filename_printed = NULL; 654 655 for (i = 0; i < PMCSTAT_NHASH; i++) { 656 LIST_INIT(&pmcstat_cgnode_hash[i]); 657 } 658 659 return (0); 660 } 661 662 void 663 pmcpl_cg_shutdown(FILE *mf) 664 { 665 int i; 666 struct pmcstat_cgnode_hash *pch, *pchtmp; 667 668 (void) mf; 669 670 if (args.pa_flags & FLAG_DO_CALLGRAPHS) 671 pmcstat_callgraph_print(); 672 673 /* 674 * Free memory. 675 */ 676 for (i = 0; i < PMCSTAT_NHASH; i++) { 677 LIST_FOREACH_SAFE(pch, &pmcstat_cgnode_hash[i], pch_next, 678 pchtmp) { 679 pmcstat_cgnode_free(pch->pch_cgnode); 680 LIST_REMOVE(pch, pch_next); 681 free(pch); 682 } 683 } 684 } 685 686