view release on metacpan or  search on metacpan

graph.h  view on Meta::CPAN

    hdr->node_bitmap_off = node_bitmap_off;
    hdr->edge_data_off   = edge_data_off;
    hdr->edge_bitmap_off = edge_bitmap_off;
    uint32_t *heads = (uint32_t *)((uint8_t *)base + node_heads_off);
    for (uint32_t i = 0; i < max_nodes; i++) heads[i] = GRAPH_NONE;
    __atomic_thread_fence(__ATOMIC_SEQ_CST);
}

static inline GraphHandle *graph_setup(void *base, size_t map_size,
                                        const char *path, int backing_fd) {
    GraphHeader *hdr = (GraphHeader *)base;
    GraphHandle *h = (GraphHandle *)calloc(1, sizeof(GraphHandle));
    if (!h) {
        munmap(base, map_size);
        if (backing_fd >= 0) close(backing_fd);
        return NULL;
    }
    h->hdr          = hdr;
    h->node_data    = (int64_t *)((uint8_t *)base + hdr->node_data_off);
    h->node_heads   = (uint32_t *)((uint8_t *)base + hdr->node_heads_off);
    h->node_bitmap  = (uint64_t *)((uint8_t *)base + hdr->node_bitmap_off);
    h->edges        = (GraphEdge *)((uint8_t *)base + hdr->edge_data_off);
    h->edge_bitmap  = (uint64_t *)((uint8_t *)base + hdr->edge_bitmap_off);
    h->node_bwords  = (hdr->max_nodes + 63) / 64;
    h->edge_bwords  = (hdr->max_edges + 63) / 64;
    h->mmap_size    = map_size;
    h->path         = path ? strdup(path) : NULL;
    h->notify_fd    = -1;
    h->backing_fd   = backing_fd;
    return h;
}

/* Validate a mapped header (shared by graph_create reopen and graph_open_fd). */
static inline int graph_validate_header(const GraphHeader *hdr, uint64_t file_size) {
    if (hdr->magic != GRAPH_MAGIC) return 0;
    if (hdr->version != GRAPH_VERSION) return 0;
    if (hdr->max_nodes == 0 || hdr->max_edges == 0) return 0;
    if (hdr->max_nodes > 0x7FFFFFFFu || hdr->max_edges > 0x7FFFFFFFu) return 0;
    if (hdr->total_size != file_size) return 0;
    if (hdr->total_size != graph_total_size(hdr->max_nodes, hdr->max_edges)) return 0;

    uint32_t nb = (hdr->max_nodes + 63) / 64;
    uint64_t exp_node_data   = sizeof(GraphHeader);
    uint64_t exp_node_heads  = exp_node_data  + (uint64_t)hdr->max_nodes * sizeof(int64_t);
    uint64_t exp_node_bitmap = exp_node_heads + (uint64_t)hdr->max_nodes * sizeof(uint32_t);
    uint64_t exp_edge_data   = exp_node_bitmap + (uint64_t)nb * 8;
    uint64_t exp_edge_bitmap = exp_edge_data   + (uint64_t)hdr->max_edges * sizeof(GraphEdge);
    if (hdr->node_data_off   != exp_node_data)   return 0;
    if (hdr->node_heads_off  != exp_node_heads)  return 0;
    if (hdr->node_bitmap_off != exp_node_bitmap) return 0;
    if (hdr->edge_data_off   != exp_edge_data)   return 0;
    if (hdr->edge_bitmap_off != exp_edge_bitmap) return 0;
    return 1;
}

/* Securely obtain a fd: create exclusively (O_CREAT|O_EXCL|O_NOFOLLOW at mode,
 * default 0600), or attach an existing file (O_RDWR|O_NOFOLLOW, no O_CREAT). */
static int graph_secure_open(const char *path, mode_t mode, char *errbuf) {
    for (int attempt = 0; attempt < 100; attempt++) {
        int fd = open(path, O_RDWR|O_CREAT|O_EXCL|O_NOFOLLOW|O_CLOEXEC, mode);
        if (fd >= 0) { (void)fchmod(fd, mode); return fd; }   /* exact mode: umask narrowed the O_EXCL create */
        if (errno != EEXIST) { GRAPH_ERR("create %s: %s", path, strerror(errno)); return -1; }
        fd = open(path, O_RDWR|O_NOFOLLOW|O_CLOEXEC);
        if (fd >= 0) return fd;
        if (errno == ENOENT) continue;   /* creator unlinked between our two opens; retry */
        GRAPH_ERR("open %s: %s", path, strerror(errno));  /* ELOOP => symlink rejected */
        return -1;
    }
    GRAPH_ERR("open %s: create/attach kept racing", path);
    return -1;
}

static GraphHandle *graph_create(const char *path, uint32_t max_nodes, uint32_t max_edges,
                                  mode_t mode, char *errbuf) {
    if (errbuf) errbuf[0] = '\0';
    if (max_nodes == 0) { GRAPH_ERR("max_nodes must be > 0"); return NULL; }
    if (max_edges == 0) { GRAPH_ERR("max_edges must be > 0"); return NULL; }
    if (max_nodes > UINT32_MAX - 63) { GRAPH_ERR("max_nodes too large"); return NULL; }
    if (max_edges > UINT32_MAX - 63) { GRAPH_ERR("max_edges too large"); return NULL; }

    /* Round max_nodes up to even so the node bitmap -- an array of uint64_t
     * touched with __atomic_fetch_or/and -- starts 8-byte aligned.  Its offset
     * is 128 + max_nodes*(8+4), 8-aligned iff max_nodes is even; an odd count
     * leaves it 4-aligned and aarch64 atomic ops SIGBUS on it.  New files only:
     * existing odd-count files keep their stored offsets and still attach. */
    max_nodes = (max_nodes + 1u) & ~1u;

    uint64_t total = graph_total_size(max_nodes, max_edges);
    int anonymous = (path == NULL);
    int fd = -1;
    size_t map_size;
    void *base;

    if (anonymous) {
        map_size = (size_t)total;
        base = mmap(NULL, map_size, PROT_READ|PROT_WRITE, MAP_SHARED|MAP_ANONYMOUS, -1, 0);
        if (base == MAP_FAILED) { GRAPH_ERR("mmap: %s", strerror(errno)); return NULL; }
    } else {
        fd = graph_secure_open(path, mode, errbuf);
        if (fd < 0) return NULL;
        if (flock(fd, LOCK_EX) < 0) { GRAPH_ERR("flock: %s", strerror(errno)); close(fd); return NULL; }
        struct stat st;
        if (fstat(fd, &st) < 0) { GRAPH_ERR("fstat: %s", strerror(errno)); flock(fd, LOCK_UN); close(fd); return NULL; }
        int is_new = (st.st_size == 0);
        if (!is_new && (uint64_t)st.st_size < sizeof(GraphHeader)) {
            GRAPH_ERR("%s: file too small (%lld)", path, (long long)st.st_size);
            flock(fd, LOCK_UN); close(fd); return NULL;
        }
        if (is_new && ftruncate(fd, (off_t)total) < 0) {
            GRAPH_ERR("ftruncate: %s", strerror(errno)); flock(fd, LOCK_UN); close(fd); return NULL;
        }
        map_size = is_new ? (size_t)total : (size_t)st.st_size;
        base = mmap(NULL, map_size, PROT_READ|PROT_WRITE, MAP_SHARED, fd, 0);
        if (base == MAP_FAILED) { GRAPH_ERR("mmap: %s", strerror(errno)); flock(fd, LOCK_UN); close(fd); return NULL; }
        if (!is_new) {
            if (!graph_validate_header((GraphHeader *)base, (uint64_t)st.st_size)) {
                GRAPH_ERR("invalid graph file"); munmap(base, map_size); flock(fd, LOCK_UN); close(fd); return NULL;
            }
            flock(fd, LOCK_UN); close(fd);
            return graph_setup(base, map_size, path, -1);
        }