palacios/src/palacios/vmm_checkpoint.c

   1 /*
   2  * This file is part of the Palacios Virtual Machine Monitor developed
   3  * by the V3VEE Project with funding from the United States National
   4  * Science Foundation and the Department of Energy.
   5  *
   6  * The V3VEE Project is a joint project between Northwestern University
   7  * and the University of New Mexico.  You can find out more at
   8  * http://www.v3vee.org
   9  *
  10  * Copyright (c) 2011, Madhav Suresh <madhav@u.northwestern.edu>
  11  * Copyright (c) 2011, The V3VEE Project <http://www.v3vee.org>
  12  * All rights reserved.
  13  *
  14  * Author: Madhav Suresh <madhav@u.northwestern.edu>
  15  *         Arefin Huq <fig@arefin.net>
  16  *
  17  *
  18  * This is free software.  You are permitted to use,
  19  * redistribute, and modify it as specified in the file "V3VEE_LICENSE".
  20  */
  21
  22 #include <palacios/vmm.h>
  23 #include <palacios/vmm_sprintf.h>
  24 #include <palacios/vm_guest.h>
  25 #include <palacios/svm.h>
  26 #include <palacios/vmx.h>
  27 #include <palacios/vmm_checkpoint.h>
  28 #include <palacios/vmm_hashtable.h>
  29 #include <palacios/vmm_direct_paging.h>
  30
  31 #include <palacios/vmm_dev_mgr.h>
  32
  33
  34 static struct hashtable * store_table = NULL;
  35
  36 struct v3_chkpt;
  37
  38 typedef enum {SAVE, LOAD} chkpt_mode_t;
  39
  40 struct chkpt_interface {
  41     char name[128];
  42     void * (*open_chkpt)(char * url, chkpt_mode_t mode);
  43     int (*close_chkpt)(void * store_data);
  44
  45     void * (*open_ctx)(void * store_data, void * parent_ctx, char * name);
  46     int (*close_ctx)(void * store_data, void * ctx);
  47
  48     int (*save)(void * store_data, void * ctx, char * tag, uint64_t len, void * buf);
  49     int (*load)(void * store_data, void * ctx, char * tag, uint64_t len, void * buf);
  50 };
  51
  52
  53 struct v3_chkpt {
  54     struct v3_vm_info * vm;
  55
  56     struct chkpt_interface * interface;
  57
  58     void * store_data;
  59 };
  60
  61
  62
  63
  64 static uint_t store_hash_fn(addr_t key) {
  65     char * name = (char *)key;
  66     return v3_hash_buffer((uint8_t *)name, strlen(name));
  67 }
  68
  69 static int store_eq_fn(addr_t key1, addr_t key2) {
  70     char * name1 = (char *)key1;
  71     char * name2 = (char *)key2;
  72
  73     return (strcmp(name1, name2) == 0);
  74 }
  75
  76
  77
  78 #include "vmm_chkpt_stores.h"
  79
  80
  81 int V3_init_checkpoint() {
  82     extern struct chkpt_interface * __start__v3_chkpt_stores[];
  83     extern struct chkpt_interface * __stop__v3_chkpt_stores[];
  84     struct chkpt_interface ** tmp_store = __start__v3_chkpt_stores;
  85     int i = 0;
  86
  87     store_table = v3_create_htable(0, store_hash_fn, store_eq_fn);
  88
  89     while (tmp_store != __stop__v3_chkpt_stores) {
  90         V3_Print("Registering Checkpoint Backing Store (%s)\n", (*tmp_store)->name);
  91
  92         if (v3_htable_search(store_table, (addr_t)((*tmp_store)->name))) {
  93             PrintError("Multiple instances of Checkpoint backing Store (%s)\n", (*tmp_store)->name);
  94             return -1;
  95         }
  96
  97         if (v3_htable_insert(store_table, (addr_t)((*tmp_store)->name), (addr_t)(*tmp_store)) == 0) {
  98             PrintError("Could not register Checkpoint backing store (%s)\n", (*tmp_store)->name);
  99             return -1;
 100         }
 101
 102         tmp_store = &(__start__v3_chkpt_stores[++i]);
 103     }
 104
 105     return 0;
 106 }
 107
 108 int V3_deinit_checkpoint() {
 109     v3_free_htable(store_table, 0, 0);
 110     return 0;
 111 }
 112
 113
 114 static char svm_chkpt_header[] = "v3vee palacios checkpoint version: x.x, SVM x.x";
 115 static char vmx_chkpt_header[] = "v3vee palacios checkpoint version: x.x, VMX x.x";
 116
 117 static int chkpt_close(struct v3_chkpt * chkpt) {
 118     chkpt->interface->close_chkpt(chkpt->store_data);
 119
 120     V3_Free(chkpt);
 121
 122     return 0;
 123 }
 124
 125
 126 static struct v3_chkpt * chkpt_open(struct v3_vm_info * vm, char * store, char * url, chkpt_mode_t mode) {
 127     struct chkpt_interface * iface = NULL;
 128     struct v3_chkpt * chkpt = NULL;
 129     void * store_data = NULL;
 130
 131     iface = (void *)v3_htable_search(store_table, (addr_t)store);
 132
 133     if (iface == NULL) {
 134         V3_Print("Error: Could not locate Checkpoint interface for store (%s)\n", store);
 135         return NULL;
 136     }
 137
 138     store_data = iface->open_chkpt(url, mode);
 139
 140     if (store_data == NULL) {
 141         PrintError("Could not open url (%s) for backing store (%s)\n", url, store);
 142         return NULL;
 143     }
 144
 145
 146     chkpt = V3_Malloc(sizeof(struct v3_chkpt));
 147
 148     if (!chkpt) {
 149         PrintError("Could not allocate checkpoint state\n");
 150         return NULL;
 151     }
 152
 153     chkpt->interface = iface;
 154     chkpt->vm = vm;
 155     chkpt->store_data = store_data;
 156
 157     return chkpt;
 158 }
 159
 160 struct v3_chkpt_ctx * v3_chkpt_open_ctx(struct v3_chkpt * chkpt, struct v3_chkpt_ctx * parent, char * name) {
 161     struct v3_chkpt_ctx * ctx = V3_Malloc(sizeof(struct v3_chkpt_ctx));
 162     void * parent_store_ctx = NULL;
 163
 164
 165     if (!ctx) {
 166         PrintError("Unable to allocate context\n");
 167         return 0;
 168     }
 169
 170     memset(ctx, 0, sizeof(struct v3_chkpt_ctx));
 171
 172     ctx->chkpt = chkpt;
 173     ctx->parent = parent;
 174
 175     if (parent) {
 176         parent_store_ctx = parent->store_ctx;
 177     }
 178
 179     ctx->store_ctx = chkpt->interface->open_ctx(chkpt->store_data, parent_store_ctx, name);
 180
 181     if (!(ctx->store_ctx)) {
 182         PrintError("Warning: opening underlying representation returned null\n");
 183     }
 184
 185     return ctx;
 186 }
 187
 188 int v3_chkpt_close_ctx(struct v3_chkpt_ctx * ctx) {
 189     struct v3_chkpt * chkpt = ctx->chkpt;
 190     int ret = 0;
 191
 192     ret = chkpt->interface->close_ctx(chkpt->store_data, ctx->store_ctx);
 193
 194     V3_Free(ctx);
 195
 196     return ret;
 197 }
 198
 199
 200
 201
 202
 203 int v3_chkpt_save(struct v3_chkpt_ctx * ctx, char * tag, uint64_t len, void * buf) {
 204     struct v3_chkpt * chkpt = ctx->chkpt;
 205
 206     return  chkpt->interface->save(chkpt->store_data, ctx->store_ctx, tag, len, buf);
 207
 208 }
 209
 210
 211 int v3_chkpt_load(struct v3_chkpt_ctx * ctx, char * tag, uint64_t len, void * buf) {
 212     struct v3_chkpt * chkpt = ctx->chkpt;
 213
 214     return chkpt->interface->load(chkpt->store_data, ctx->store_ctx, tag, len, buf);
 215 }
 216
 217
 218
 219 static int load_memory(struct v3_vm_info * vm, struct v3_chkpt * chkpt) {
 220
 221     void * guest_mem_base = NULL;
 222     void * ctx = NULL;
 223     uint64_t ret = 0;
 224
 225     guest_mem_base = V3_VAddr((void *)vm->mem_map.base_region.host_addr);
 226
 227     ctx = v3_chkpt_open_ctx(chkpt, NULL, "memory_img");
 228
 229     if (!ctx) {
 230         PrintError("Unable to open context for memory load\n");
 231         return -1;
 232     }
 233
 234     if (v3_chkpt_load(ctx, "memory_img", vm->mem_size, guest_mem_base) == -1) {
 235         PrintError("Unable to load all of memory (requested=%llu bytes, result=%llu bytes\n",(uint64_t)(vm->mem_size),ret);
 236         v3_chkpt_close_ctx(ctx);
 237         return -1;
 238     }
 239
 240     v3_chkpt_close_ctx(ctx);
 241
 242     return 0;
 243 }
 244
 245
 246 static int save_memory(struct v3_vm_info * vm, struct v3_chkpt * chkpt) {
 247     void * guest_mem_base = NULL;
 248     void * ctx = NULL;
 249     uint64_t ret = 0;
 250
 251     guest_mem_base = V3_VAddr((void *)vm->mem_map.base_region.host_addr);
 252
 253     ctx = v3_chkpt_open_ctx(chkpt, NULL,"memory_img");
 254
 255     if (!ctx) {
 256         PrintError("Unable to open context to save memory\n");
 257         return -1;
 258     }
 259
 260     if (v3_chkpt_save(ctx, "memory_img", vm->mem_size, guest_mem_base) == -1) {
 261         PrintError("Unable to load all of memory (requested=%llu, received=%llu)\n",(uint64_t)(vm->mem_size),ret);
 262         v3_chkpt_close_ctx(ctx);
 263         return -1;
 264     }
 265
 266     v3_chkpt_close_ctx(ctx);
 267
 268     return 0;
 269 }
 270
 271 int save_header(struct v3_vm_info * vm, struct v3_chkpt * chkpt) {
 272     extern v3_cpu_arch_t v3_mach_type;
 273     void * ctx = NULL;
 274
 275     ctx = v3_chkpt_open_ctx(chkpt, NULL, "header");
 276     if (!ctx) {
 277         PrintError("Cannot open context to save header\n");
 278         return -1;
 279     }
 280
 281     switch (v3_mach_type) {
 282         case V3_SVM_CPU:
 283         case V3_SVM_REV3_CPU: {
 284             if (v3_chkpt_save(ctx, "header", strlen(svm_chkpt_header), svm_chkpt_header) == -1) {
 285                 PrintError("Could not save all of SVM header\n");
 286                 v3_chkpt_close_ctx(ctx);
 287                 return -1;
 288             }
 289             break;
 290         }
 291         case V3_VMX_CPU:
 292         case V3_VMX_EPT_CPU:
 293         case V3_VMX_EPT_UG_CPU: {
 294             if (v3_chkpt_save(ctx, "header", strlen(vmx_chkpt_header), vmx_chkpt_header) == -1) {
 295                 PrintError("Could not save all of VMX header\n");
 296                 v3_chkpt_close_ctx(ctx);
 297                 return -1;
 298             }
 299             break;
 300         }
 301         default:
 302             PrintError("checkpoint not supported on this architecture\n");
 303             v3_chkpt_close_ctx(ctx);
 304             return -1;
 305     }
 306
 307     v3_chkpt_close_ctx(ctx);
 308
 309     return 0;
 310 }
 311
 312 static int load_header(struct v3_vm_info * vm, struct v3_chkpt * chkpt) {
 313     extern v3_cpu_arch_t v3_mach_type;
 314     void * ctx = NULL;
 315
 316     ctx = v3_chkpt_open_ctx(chkpt, NULL, "header");
 317
 318     switch (v3_mach_type) {
 319         case V3_SVM_CPU:
 320         case V3_SVM_REV3_CPU: {
 321             char header[strlen(svm_chkpt_header) + 1];
 322
 323             if (v3_chkpt_load(ctx, "header", strlen(svm_chkpt_header), header) == -1) {
 324                 PrintError("Could not load all of SVM header\n");
 325                 v3_chkpt_close_ctx(ctx);
 326                 return -1;
 327             }
 328
 329             header[strlen(svm_chkpt_header)] = 0;
 330
 331             break;
 332         }
 333         case V3_VMX_CPU:
 334         case V3_VMX_EPT_CPU:
 335         case V3_VMX_EPT_UG_CPU: {
 336             char header[strlen(vmx_chkpt_header) + 1];
 337
 338             if (v3_chkpt_load(ctx, "header", strlen(vmx_chkpt_header), header) == -1) {
 339                 PrintError("Could not load all of VMX header\n");
 340                 v3_chkpt_close_ctx(ctx);
 341                 return -1;
 342             }
 343
 344             header[strlen(vmx_chkpt_header)] = 0;
 345
 346             break;
 347         }
 348         default:
 349             PrintError("checkpoint not supported on this architecture\n");
 350             v3_chkpt_close_ctx(ctx);
 351             return -1;
 352     }
 353
 354     v3_chkpt_close_ctx(ctx);
 355
 356     return 0;
 357 }
 358
 359
 360 static int load_core(struct guest_info * info, struct v3_chkpt * chkpt) {
 361     extern v3_cpu_arch_t v3_mach_type;
 362     void * ctx = NULL;
 363     char key_name[16];
 364
 365     memset(key_name, 0, 16);
 366
 367     snprintf(key_name, 16, "guest_info%d", info->vcpu_id);
 368
 369     ctx = v3_chkpt_open_ctx(chkpt, NULL, key_name);
 370
 371     if (!ctx) {
 372         PrintError("Could not open context to load core\n");
 373         return -1;
 374     }
 375
 376     // These really need to have error checking
 377
 378     v3_chkpt_load_64(ctx, "RIP", &(info->rip));
 379
 380     V3_CHKPT_STD_LOAD(ctx, info->vm_regs);
 381
 382     V3_CHKPT_STD_LOAD(ctx, info->ctrl_regs.cr0);
 383     V3_CHKPT_STD_LOAD(ctx, info->ctrl_regs.cr2);
 384     V3_CHKPT_STD_LOAD(ctx, info->ctrl_regs.cr4);
 385     V3_CHKPT_STD_LOAD(ctx, info->ctrl_regs.cr8);
 386     V3_CHKPT_STD_LOAD(ctx, info->ctrl_regs.rflags);
 387     V3_CHKPT_STD_LOAD(ctx, info->ctrl_regs.efer);
 388
 389     V3_CHKPT_STD_LOAD(ctx, info->dbg_regs);
 390     V3_CHKPT_STD_LOAD(ctx, info->segments);
 391     V3_CHKPT_STD_LOAD(ctx, info->shdw_pg_state.guest_cr3);
 392     V3_CHKPT_STD_LOAD(ctx, info->shdw_pg_state.guest_cr0);
 393     V3_CHKPT_STD_LOAD(ctx, info->shdw_pg_state.guest_efer);
 394
 395     v3_chkpt_close_ctx(ctx);
 396
 397     PrintDebug("Finished reading guest_info information\n");
 398
 399     info->cpu_mode = v3_get_vm_cpu_mode(info);
 400     info->mem_mode = v3_get_vm_mem_mode(info);
 401
 402     if (info->shdw_pg_mode == SHADOW_PAGING) {
 403         if (v3_get_vm_mem_mode(info) == VIRTUAL_MEM) {
 404             if (v3_activate_shadow_pt(info) == -1) {
 405                 PrintError("Failed to activate shadow page tables\n");
 406                 return -1;
 407             }
 408         } else {
 409             if (v3_activate_passthrough_pt(info) == -1) {
 410                 PrintError("Failed to activate passthrough page tables\n");
 411                 return -1;
 412             }
 413         }
 414     }
 415
 416
 417     switch (v3_mach_type) {
 418         case V3_SVM_CPU:
 419         case V3_SVM_REV3_CPU: {
 420             char key_name[16];
 421
 422             snprintf(key_name, 16, "vmcb_data%d", info->vcpu_id);
 423             ctx = v3_chkpt_open_ctx(chkpt, NULL, key_name);
 424
 425             if (!ctx) {
 426                 PrintError("Could not open context to load SVM core\n");
 427                 return -1;
 428             }
 429
 430             if (v3_svm_load_core(info, ctx) == -1) {
 431                 PrintError("Failed to patch core %d\n", info->vcpu_id);
 432                 v3_chkpt_close_ctx(ctx);
 433                 return -1;
 434             }
 435
 436             v3_chkpt_close_ctx(ctx);
 437
 438             break;
 439         }
 440         case V3_VMX_CPU:
 441         case V3_VMX_EPT_CPU:
 442         case V3_VMX_EPT_UG_CPU: {
 443             char key_name[16];
 444
 445             snprintf(key_name, 16, "vmcs_data%d", info->vcpu_id);
 446
 447             ctx = v3_chkpt_open_ctx(chkpt, NULL, key_name);
 448
 449             if (!ctx) {
 450                 PrintError("Could not open context to load VMX core\n");
 451                 return -1;
 452             }
 453
 454             if (v3_vmx_load_core(info, ctx) < 0) {
 455                 PrintError("VMX checkpoint failed\n");
 456                 v3_chkpt_close_ctx(ctx);
 457                 return -1;
 458             }
 459
 460             v3_chkpt_close_ctx(ctx);
 461
 462             break;
 463         }
 464         default:
 465             PrintError("Invalid CPU Type (%d)\n", v3_mach_type);
 466             return -1;
 467     }
 468
 469     v3_print_guest_state(info);
 470
 471     return 0;
 472 }
 473
 474
 475 static int save_core(struct guest_info * info, struct v3_chkpt * chkpt) {
 476     extern v3_cpu_arch_t v3_mach_type;
 477     void * ctx = NULL;
 478     char key_name[16];
 479
 480     memset(key_name, 0, 16);
 481
 482     v3_print_guest_state(info);
 483
 484
 485     snprintf(key_name, 16, "guest_info%d", info->vcpu_id);
 486
 487     ctx = v3_chkpt_open_ctx(chkpt, NULL, key_name);
 488
 489     if (!ctx) {
 490         PrintError("Unable to open context to save core\n");
 491         return -1;
 492     }
 493
 494
 495     // Error checking of all this needs to happen
 496     v3_chkpt_save_64(ctx, "RIP", &(info->rip));
 497
 498     V3_CHKPT_STD_SAVE(ctx, info->vm_regs);
 499
 500     V3_CHKPT_STD_SAVE(ctx, info->ctrl_regs.cr0);
 501     V3_CHKPT_STD_SAVE(ctx, info->ctrl_regs.cr2);
 502     V3_CHKPT_STD_SAVE(ctx, info->ctrl_regs.cr4);
 503     V3_CHKPT_STD_SAVE(ctx, info->ctrl_regs.cr8);
 504     V3_CHKPT_STD_SAVE(ctx, info->ctrl_regs.rflags);
 505     V3_CHKPT_STD_SAVE(ctx, info->ctrl_regs.efer);
 506
 507     V3_CHKPT_STD_SAVE(ctx, info->dbg_regs);
 508     V3_CHKPT_STD_SAVE(ctx, info->segments);
 509     V3_CHKPT_STD_SAVE(ctx, info->shdw_pg_state.guest_cr3);
 510     V3_CHKPT_STD_SAVE(ctx, info->shdw_pg_state.guest_cr0);
 511     V3_CHKPT_STD_SAVE(ctx, info->shdw_pg_state.guest_efer);
 512
 513     v3_chkpt_close_ctx(ctx);
 514
 515     //Architechture specific code
 516     switch (v3_mach_type) {
 517         case V3_SVM_CPU:
 518         case V3_SVM_REV3_CPU: {
 519             char key_name[16];
 520             void * ctx = NULL;
 521
 522             snprintf(key_name, 16, "vmcb_data%d", info->vcpu_id);
 523
 524             ctx = v3_chkpt_open_ctx(chkpt, NULL, key_name);
 525
 526             if (!ctx) {
 527                 PrintError("Could not open context to store SVM core\n");
 528                 return -1;
 529             }
 530
 531             if (v3_svm_save_core(info, ctx) == -1) {
 532                 PrintError("VMCB Unable to be written\n");
 533                 v3_chkpt_close_ctx(ctx);
 534                 return -1;
 535             }
 536
 537             v3_chkpt_close_ctx(ctx);
 538             break;
 539         }
 540         case V3_VMX_CPU:
 541         case V3_VMX_EPT_CPU:
 542         case V3_VMX_EPT_UG_CPU: {
 543             char key_name[16];
 544             void * ctx = NULL;
 545
 546             snprintf(key_name, 16, "vmcs_data%d", info->vcpu_id);
 547
 548             ctx = v3_chkpt_open_ctx(chkpt, NULL, key_name);
 549
 550             if (!ctx) {
 551                 PrintError("Could not open context to store VMX core\n");
 552                 return -1;
 553             }
 554
 555             if (v3_vmx_save_core(info, ctx) == -1) {
 556                 PrintError("VMX checkpoint failed\n");
 557                 v3_chkpt_close_ctx(ctx);
 558                 return -1;
 559             }
 560
 561             v3_chkpt_close_ctx(ctx);
 562
 563             break;
 564         }
 565         default:
 566             PrintError("Invalid CPU Type (%d)\n", v3_mach_type);
 567             return -1;
 568     }
 569
 570     return 0;
 571 }
 572
 573
 574 int v3_chkpt_save_vm(struct v3_vm_info * vm, char * store, char * url) {
 575     struct v3_chkpt * chkpt = NULL;
 576     int ret = 0;;
 577     int i = 0;
 578
 579     chkpt = chkpt_open(vm, store, url, SAVE);
 580
 581     if (chkpt == NULL) {
 582         PrintError("Error creating checkpoint store for url %s\n",url);
 583         return -1;
 584     }
 585
 586     /* If this guest is running we need to block it while the checkpoint occurs */
 587     if (vm->run_state == VM_RUNNING) {
 588         while (v3_raise_barrier(vm, NULL) == -1);
 589     }
 590
 591     if ((ret = save_memory(vm, chkpt)) == -1) {
 592         PrintError("Unable to save memory\n");
 593         goto out;
 594     }
 595
 596
 597     if ((ret = v3_save_vm_devices(vm, chkpt)) == -1) {
 598         PrintError("Unable to save devices\n");
 599         goto out;
 600     }
 601
 602
 603     if ((ret = save_header(vm, chkpt)) == -1) {
 604         PrintError("Unable to save header\n");
 605         goto out;
 606     }
 607
 608     for (i = 0; i < vm->num_cores; i++){
 609         if ((ret = save_core(&(vm->cores[i]), chkpt)) == -1) {
 610             PrintError("chkpt of core %d failed\n", i);
 611             goto out;
 612         }
 613     }
 614
 615  out:
 616
 617     /* Resume the guest if it was running */
 618     if (vm->run_state == VM_RUNNING) {
 619         v3_lower_barrier(vm);
 620     }
 621
 622     chkpt_close(chkpt);
 623
 624     return ret;
 625
 626 }
 627
 628 int v3_chkpt_load_vm(struct v3_vm_info * vm, char * store, char * url) {
 629     struct v3_chkpt * chkpt = NULL;
 630     int i = 0;
 631     int ret = 0;
 632
 633     chkpt = chkpt_open(vm, store, url, LOAD);
 634
 635     if (chkpt == NULL) {
 636         PrintError("Error creating checkpoint store\n");
 637         return -1;
 638     }
 639
 640     /* If this guest is running we need to block it while the checkpoint occurs */
 641     if (vm->run_state == VM_RUNNING) {
 642         while (v3_raise_barrier(vm, NULL) == -1);
 643     }
 644
 645     if ((ret = load_memory(vm, chkpt)) == -1) {
 646         PrintError("Unable to save memory\n");
 647         goto out;
 648     }
 649
 650
 651     if ((ret = v3_load_vm_devices(vm, chkpt)) == -1) {
 652         PrintError("Unable to load devies\n");
 653         goto out;
 654     }
 655
 656
 657     if ((ret = load_header(vm, chkpt)) == -1) {
 658         PrintError("Unable to load header\n");
 659         goto out;
 660     }
 661
 662     //per core cloning
 663     for (i = 0; i < vm->num_cores; i++) {
 664         if ((ret = load_core(&(vm->cores[i]), chkpt)) == -1) {
 665             PrintError("Error loading core state (core=%d)\n", i);
 666             goto out;
 667         }
 668     }
 669
 670  out:
 671
 672     /* Resume the guest if it was running and we didn't just trash the state*/
 673     if (vm->run_state == VM_RUNNING) {
 674
 675         if (ret == -1) {
 676             vm->run_state = VM_STOPPED;
 677         }
 678
 679         /* We check the run state of the VM after every barrier
 680            So this will immediately halt the VM
 681         */
 682         v3_lower_barrier(vm);
 683     }
 684
 685     chkpt_close(chkpt);
 686
 687     return ret;
 688 }
 689
 690
 691