c - 使用大型输入文件时使用三角形软件出现分割错误

Question

我正在使用 Triangle 软件(二维质量网格生成器和 Delaunay 三角器)( https://www.cs.cmu.edu/~quake/triangle.html ) 进行网格生成。它是开源的。

当我尝试使用包含 639,896,119 个节点、大小为 24 GB 的 .node 文件创建网格时，出现段错误。我不确定是内存的问题，我的机器是32 GB内存，所以我在504 GB内存的 super 计算机上运行它。它还给出了段错误。

.node文件是具有格式的文本文件

    1 x1 y1 z1
    2 x2 y2 z2
...

gdb 调试在函数 readnodes() 内的第 #14029 行给出了段错误。我用 printft() 来查看它何时崩溃，它最多可以读取 103,025,230 行。 readnoedes()是读取.node文件的每一行。

我在此处附加了 readnodes() 函数。发生分段的行已标记://帮助，gdb 在读取了很多行后在这里给出了段错误。

非常感谢任何帮助!

/*****************************************************************************/
/*                                                                           */
/*  readnodes()   Read the vertices from a file, which may be a .node or     */
/*                .poly file.                                                */
/*                                                                           */
/*****************************************************************************/

#ifndef TRILIBRARY

#ifdef ANSI_DECLARATORS
void readnodes(struct mesh *m, struct behavior *b, char *nodefilename,
               char *polyfilename, FILE **polyfile)
#else /* not ANSI_DECLARATORS */
void readnodes(m, b, nodefilename, polyfilename, polyfile)
struct mesh *m;
struct behavior *b;
char *nodefilename;
char *polyfilename;
FILE **polyfile;
#endif /* not ANSI_DECLARATORS */

{
  FILE *infile;
  vertex vertexloop;
  char inputline[INPUTLINESIZE];
  char *stringptr;
  char *infilename;
  REAL x, y;
  int firstnode;
  int nodemarkers;
  int currentmarker;
  int i, j;

  if (b->poly) {
    /* Read the vertices from a .poly file. */
    if (!b->quiet) {
      printf("Opening %s.\n", polyfilename);
    }
    *polyfile = fopen(polyfilename, "r");
    if (*polyfile == (FILE *) NULL) {
      printf("  Error:  Cannot access file %s.\n", polyfilename);
      triexit(1);
    }
    /* Read number of vertices, number of dimensions, number of vertex */
    /*   attributes, and number of boundary markers.                   */
    stringptr = readline(inputline, *polyfile, polyfilename);
    m->invertices = (int) strtol(stringptr, &stringptr, 0);
    stringptr = findfield(stringptr);
    if (*stringptr == '\0') {
      m->mesh_dim = 2;
    } else {
      m->mesh_dim = (int) strtol(stringptr, &stringptr, 0);
    }
    stringptr = findfield(stringptr);
    if (*stringptr == '\0') {
      m->nextras = 0;
    } else {
      m->nextras = (int) strtol(stringptr, &stringptr, 0);
    }
    stringptr = findfield(stringptr);
    if (*stringptr == '\0') {
      nodemarkers = 0;
    } else {
      nodemarkers = (int) strtol(stringptr, &stringptr, 0);
    }
    if (m->invertices > 0) {
      infile = *polyfile;
      infilename = polyfilename;
      m->readnodefile = 0;
    } else {
      /* If the .poly file claims there are zero vertices, that means that */
      /*   the vertices should be read from a separate .node file.         */
      m->readnodefile = 1;
      infilename = nodefilename;
    }
  } else {
    m->readnodefile = 1;
    infilename = nodefilename;
    *polyfile = (FILE *) NULL;
  }

  if (m->readnodefile) {
    /* Read the vertices from a .node file. */
    if (!b->quiet) {
      printf("Opening %s.\n", nodefilename);
    }
    infile = fopen(nodefilename, "r");
    if (infile == (FILE *) NULL) {
      printf("  Error:  Cannot access file %s.\n", nodefilename);
      triexit(1);
    }
    /* Read number of vertices, number of dimensions, number of vertex */
    /*   attributes, and number of boundary markers.                   */
    stringptr = readline(inputline, infile, nodefilename);
    m->invertices = (int) strtol(stringptr, &stringptr, 0);
    stringptr = findfield(stringptr);
    if (*stringptr == '\0') {
      m->mesh_dim = 2;
    } else {
      m->mesh_dim = (int) strtol(stringptr, &stringptr, 0);
    }
    stringptr = findfield(stringptr);
    if (*stringptr == '\0') {
      m->nextras = 0;
    } else {
      m->nextras = (int) strtol(stringptr, &stringptr, 0);
    }
    stringptr = findfield(stringptr);
    if (*stringptr == '\0') {
      nodemarkers = 0;
    } else {
      nodemarkers = (int) strtol(stringptr, &stringptr, 0);
    }
  }

  if (m->invertices < 3) {
    printf("Error:  Input must have at least three input vertices.\n");
    triexit(1);
  }
  if (m->mesh_dim != 2) {
    printf("Error:  Triangle only works with two-dimensional meshes.\n");
    triexit(1);
  }
  if (m->nextras == 0) {
    b->weighted = 0;
  }

  initializevertexpool(m, b);

  /* Read the vertices. */
  for (i = 0; i < m->invertices; i++) {
    vertexloop = (vertex) poolalloc(&m->vertices);
    stringptr = readline(inputline, infile, infilename);
    if (i == 0) {
      firstnode = (int) strtol(stringptr, &stringptr, 0);
      if ((firstnode == 0) || (firstnode == 1)) {
        b->firstnumber = firstnode;
      }
    }
    stringptr = findfield(stringptr);
    if (*stringptr == '\0') {
      printf("Error:  Vertex %d has no x coordinate.\n", b->firstnumber + i);
      triexit(1);
    }
    x = (REAL) strtod(stringptr, &stringptr);
    stringptr = findfield(stringptr);
    if (*stringptr == '\0') {
      printf("Error:  Vertex %d has no y coordinate.\n", b->firstnumber + i);
      triexit(1);
    }
    y = (REAL) strtod(stringptr, &stringptr);
    vertexloop[0] = x; // HELP, gdb gave segmentation fault here after reading a lot lines.  
    vertexloop[1] = y;
    /* Read the vertex attributes. */
    for (j = 2; j < 2 + m->nextras; j++) {
      stringptr = findfield(stringptr);
      if (*stringptr == '\0') {
        vertexloop[j] = 0.0;
      } else {
        vertexloop[j] = (REAL) strtod(stringptr, &stringptr);
      }
    }
    if (nodemarkers) {
      /* Read a vertex marker. */
      stringptr = findfield(stringptr);
      if (*stringptr == '\0') {
        setvertexmark(vertexloop, 0);
      } else {
        currentmarker = (int) strtol(stringptr, &stringptr, 0);
        setvertexmark(vertexloop, currentmarker);
      }
    } else {
      /* If no markers are specified in the file, they default to zero. */
      setvertexmark(vertexloop, 0);
    }
    setvertextype(vertexloop, INPUTVERTEX);
    /* Determine the smallest and largest x and y coordinates. */
    if (i == 0) {
      m->xmin = m->xmax = x;
      m->ymin = m->ymax = y;
    } else {
      m->xmin = (x < m->xmin) ? x : m->xmin;
      m->xmax = (x > m->xmax) ? x : m->xmax;
      m->ymin = (y < m->ymin) ? y : m->ymin;
      m->ymax = (y > m->ymax) ? y : m->ymax;
    }
  }
  if (m->readnodefile) {
    fclose(infile);
  }

  /* Nonexistent x value used as a flag to mark circle events in sweepline */
  /*   Delaunay algorithm.                                                 */
  m->xminextreme = 10 * m->xmin - 9 * m->xmax;
}

#endif /* not TRILIBRARY */


/*****************************************************************************/
/*                                                                           */
/*  poolalloc()   Allocate space for an item.                                */
/*                                                                           */
/*****************************************************************************/

#ifdef ANSI_DECLARATORS
VOID *poolalloc(struct memorypool *pool)
#else /* not ANSI_DECLARATORS */
VOID *poolalloc(pool)
struct memorypool *pool;
#endif /* not ANSI_DECLARATORS */

{
  VOID *newitem;
  VOID **newblock;
  unsigned long alignptr;

  /* First check the linked list of dead items.  If the list is not   */
  /*   empty, allocate an item from the list rather than a fresh one. */
  if (pool->deaditemstack != (VOID *) NULL) {
    newitem = pool->deaditemstack;               /* Take first item in list. */
    pool->deaditemstack = * (VOID **) pool->deaditemstack;
  } else {
    /* Check if there are any free items left in the current block. */
    if (pool->unallocateditems == 0) {
      /* Check if another block must be allocated. */
      if (*(pool->nowblock) == (VOID *) NULL) {
        /* Allocate a new block of items, pointed to by the previous block. */
        newblock = (VOID **) trimalloc(pool->itemsperblock * pool->itembytes +
                                       (int) sizeof(VOID *) +
                                       pool->alignbytes);
        *(pool->nowblock) = (VOID *) newblock;
        /* The next block pointer is NULL. */
        *newblock = (VOID *) NULL;
      }

      /* Move to the new block. */
      pool->nowblock = (VOID **) *(pool->nowblock);
      /* Find the first item in the block.    */
      /*   Increment by the size of (VOID *). */
      alignptr = (unsigned long) (pool->nowblock + 1);
      /* Align the item on an `alignbytes'-byte boundary. */
      pool->nextitem = (VOID *)
        (alignptr + (unsigned long) pool->alignbytes -
         (alignptr % (unsigned long) pool->alignbytes));
      /* There are lots of unallocated items left in this block. */
      pool->unallocateditems = pool->itemsperblock;
    }

    /* Allocate a new item. */
    newitem = pool->nextitem;
    /* Advance `nextitem' pointer to next free item in block. */
    pool->nextitem = (VOID *) ((char *) pool->nextitem + pool->itembytes);
    pool->unallocateditems--;
    pool->maxitems++;
  }
  pool->items++;
  return newitem;
}

/*****************************************************************************/
/*                                                                           */
/*  pooldealloc()   Deallocate space for an item.                            */
/*                                                                           */
/*  The deallocated space is stored in a queue for later reuse.              */
/*                                                                           */
/*****************************************************************************/

#ifdef ANSI_DECLARATORS
void pooldealloc(struct memorypool *pool, VOID *dyingitem)
#else /* not ANSI_DECLARATORS */
void pooldealloc(pool, dyingitem)
struct memorypool *pool;
VOID *dyingitem;
#endif /* not ANSI_DECLARATORS */

{
  /* Push freshly killed item onto stack. */
  *((VOID **) dyingitem) = pool->deaditemstack;
  pool->deaditemstack = dyingitem;
  pool->items--;
}

@MitchWheat，这是 Valgrind 的输出。任何想法？

`Opening thames_5m.node.
==8904== Memcheck, a memory error detector
==8904== Copyright (C) 2002-2012, and GNU GPL'd, by Julian Seward et al.
==8904== Using Valgrind-3.8.1 and LibVEX; rerun with -h for copyright info
==8904== Command: ./triangle thames_5m.node
==8904==
==8904== Warning: set address range perms: large range [0x3aeef040, 0xff703730) (undefined)
==8904== Invalid write of size 8
==8904==    at 0x419FE0: readnodes (triangle.c:14033)
==8904==    by 0x41C17B: main (triangle.c:15727)
==8904==  Address 0xff703730 is 0 bytes after a block of size 3,296,806,640 alloc'd
==8904==    at 0x4A06A2E: malloc (vg_replace_malloc.c:270)
==8904==    by 0x400CB9: trimalloc (triangle.c:1431)
==8904==    by 0x4044F9: poolinit (triangle.c:3967)
==8904==    by 0x40485B: initializevertexpool (triangle.c:4295)
==8904==    by 0x419EB8: readnodes (triangle.c:14005)
==8904==    by 0x41C17B: main (triangle.c:15727)
==8904==
==8904== Invalid write of size 8
==8904==    at 0x419FE6: readnodes (triangle.c:14034)
==8904==    by 0x41C17B: main (triangle.c:15727)
==8904==  Address 0xff703738 is 8 bytes after a block of size 3,296,806,640 alloc'd
==8904==    at 0x4A06A2E: malloc (vg_replace_malloc.c:270)
==8904==    by 0x400CB9: trimalloc (triangle.c:1431)
==8904==    by 0x4044F9: poolinit (triangle.c:3967)
==8904==    by 0x40485B: initializevertexpool (triangle.c:4295)
==8904==    by 0x419EB8: readnodes (triangle.c:14005)
==8904==    by 0x41C17B: main (triangle.c:15727)
==8904==
==8904== Invalid write of size 8
==8904==    at 0x41A036: readnodes (triangle.c:14041)
==8904==    by 0x41C17B: main (triangle.c:15727)
==8904==  Address 0xff703740 is 16 bytes after a block of size 3,296,806,640 alloc'd
==8904==    at 0x4A06A2E: malloc (vg_replace_malloc.c:270)
==8904==    by 0x400CB9: trimalloc (triangle.c:1431)
==8904==    by 0x4044F9: poolinit (triangle.c:3967)
==8904==    by 0x40485B: initializevertexpool (triangle.c:4295)
==8904==    by 0x419EB8: readnodes (triangle.c:14005)
==8904==    by 0x41C17B: main (triangle.c:15727)
==8904==
==8904== Invalid write of size 4
==8904==    at 0x41A0A2: readnodes (triangle.c:14055)
==8904==    by 0x41C17B: main (triangle.c:15727)
==8904==  Address 0xff703748 is not stack'd, malloc'd or (recently) free'd
==8904==
==8904== Invalid write of size 4
==8904==    at 0x41A0B1: readnodes (triangle.c:14057)
==8904==    by 0x41C17B: main (triangle.c:15727)
==8904==  Address 0xff70374c is not stack'd, malloc'd or (recently) free'd
==8904==
==8904==
==8904== Process terminating with default action of signal 11 (SIGSEGV): dumping core
==8904==  Access not within mapped region at address 0xFF704000
==8904==    at 0x41A036: readnodes (triangle.c:14041)
==8904==    by 0x41C17B: main (triangle.c:15727)
==8904==  If you believe this happened as a result of a stack
==8904==  overflow in your program's main thread (unlikely but
==8904==  possible), you can try to increase the size of the
==8904==  main thread stack using the --main-stacksize= flag.
==8904==  The main thread stack size used in this run was 10485760.
==8904==
==8904== HEAP SUMMARY:
==8904==     in use at exit: 3,296,807,208 bytes in 2 blocks
==8904==   total heap usage: 2 allocs, 0 frees, 3,296,807,208 bytes allocated
==8904==
==8904== LEAK SUMMARY:
==8904==    definitely lost: 0 bytes in 0 blocks
==8904==    indirectly lost: 0 bytes in 0 blocks
==8904==      possibly lost: 0 bytes in 0 blocks
==8904==    still reachable: 3,296,807,208 bytes in 2 blocks
==8904==         suppressed: 0 bytes in 0 blocks
==8904== Reachable blocks (those to which a pointer was found) are not shown.
==8904== To see them, rerun with: --leak-check=full --show-reachable=yes
==8904==
==8904== For counts of detected and suppressed errors, rerun with: -v
==8904== ERROR SUMMARY: 353 errors from 5 contexts (suppressed: 6 from 6)



                                            1,1           Top
`

Answer 1

vertexloop 由自定义函数这样分配:

vertexloop = (vertex) poolalloc(&m->vertices);

您应该测试 vertexloop 是否为 NULL 并使用有意义的消息中止。

如果这告诉您无法分配内存，请调查poolalloc以查看是否存在导致大型计算机上分配失败的任何限制，这些限制可能是操作系统通过配额施加的。使用 malloc 编写一个简单的分配测试并查看何时失败。