collab/1brc

the one billion row challenge

git clone https://git.julia.blue/collab/1brc

Rahul Butaniexp/file-io: NUMA aware page cache population/hugetlbfs set up4f6de22

main
6.2 KiB252 linesraw
1// cc -lnuma
2
3#define _GNU_SOURCE
4#include <errno.h>
5#include <fcntl.h>
6#include <inttypes.h>
7#include <sched.h>
8#include <stdint.h>
9#include <stdio.h>
10#include <stdlib.h>
11#include <string.h>
12#include <sys/mman.h>
13#include <sys/stat.h>
14#include <sys/statfs.h>
15#include <sys/types.h>
16#include <sys/wait.h>
17#include <unistd.h>
18
19#include <numa.h>
20#include <numaif.h>
21
22#ifndef HUGETLBFS_MAGIC
23#define HUGETLBFS_MAGIC 0x958458f6
24#endif
25
26static void die(const char *msg) {
27  int e = errno;
28  fprintf(stderr, "%s: %s\n", msg, strerror(e));
29  exit(1);
30}
31
32static size_t round_up_size(size_t x, size_t a) {
33  return (x + a - 1) / a * a;
34}
35
36static size_t detect_hugepage_size_from_path(const char *path) {
37  struct statfs s;
38  if (statfs(path, &s) == 0) {
39    if ((unsigned long)s.f_type == (unsigned long)HUGETLBFS_MAGIC && s.f_bsize > 0) {
40      return (size_t)s.f_bsize;
41    }
42    if (s.f_bsize > 0 && (size_t)s.f_bsize >= 4096)
43      return (size_t)s.f_bsize;
44  }
45  return 2u * 1024u * 1024u;
46}
47
48struct numa_node_info {
49  int node;
50  int cpu_count;
51  cpu_set_t cpuset;
52};
53
54static void copy_range(
55  int fd, size_t in_size, void *dst, size_t start, size_t length
56) {
57  const size_t buf_sz = 1024 * 1024;
58  char *buf = malloc(buf_sz);
59  if (!buf) die("malloc failed");
60
61  if (lseek(fd, (off_t)start, SEEK_SET) < 0) die("lseek(input) failed");
62
63  size_t remaining = length;
64  size_t copied = 0;
65  while (remaining > 0 && (start + copied) < in_size) {
66    size_t want = remaining;
67    if (want > buf_sz) want = buf_sz;
68    if (start + copied + want > in_size) {
69      want = in_size - (start + copied);
70      if (want == 0) break;
71    }
72
73    ssize_t n = read(fd, buf, want);
74    if (n < 0) die("read failed");
75    if (n == 0) break;
76
77    memcpy((char *)dst + start + copied, buf, (size_t)n);
78    copied += (size_t)n;
79    remaining -= (size_t)n;
80  }
81
82  free(buf);
83}
84
85static void setup_numa(
86  struct numa_node_info **out_nodes, int *out_nnodes, long *out_total_weight
87) {
88  if (numa_available() < 0) {
89    die("NUMA requested but libnuma reports unavailable");
90  }
91
92  int max_node = numa_max_node();
93  int nnodes = 0;
94
95  struct numa_node_info *nodes =
96      calloc((size_t)(max_node + 1), sizeof(struct numa_node_info));
97  if (!nodes) die("calloc nodes failed");
98
99  long total_weight = 0;
100
101  for (int n = 0; n <= max_node; n++) {
102    if (!numa_bitmask_isbitset(numa_all_nodes_ptr, n))
103      continue;
104
105    cpu_set_t cpuset;
106    CPU_ZERO(&cpuset);
107
108    struct bitmask *bm = numa_allocate_cpumask();
109    if (!bm) die("numa_allocate_cpumask failed");
110
111    if (numa_node_to_cpus(n, bm) != 0) {
112      numa_free_cpumask(bm);
113      continue;
114    }
115
116    int cpu_count = 0;
117    for (int c = 0; c < bm->size; c++) {
118      if (numa_bitmask_isbitset(bm, c)) {
119        CPU_SET(c, &cpuset);
120        cpu_count++;
121      }
122    }
123
124    numa_free_cpumask(bm);
125
126    if (cpu_count == 0)
127      continue;
128
129    nodes[nnodes].node = n;
130    nodes[nnodes].cpu_count = cpu_count;
131    nodes[nnodes].cpuset = cpuset;
132    total_weight += cpu_count;
133    nnodes++;
134  }
135
136  if (nnodes == 0) {
137    free(nodes);
138    die("NUMA requested but no nodes with CPUs found, falling back");
139  }
140
141  *out_nodes = nodes;
142  *out_nnodes = nnodes;
143  *out_total_weight = total_weight;
144}
145
146int main(int argc, char **argv) {
147  if (argc != 3) {
148    fprintf(stderr, "usage: %s <input file> <output path under hugetlbfs mount>\n", argv[0]);
149    return 2;
150  }
151
152  const char *in_path = argv[1];
153  const char *out_path = argv[2];
154
155  int in_fd = open(in_path, O_RDONLY);
156  if (in_fd < 0) die("open(input) failed");
157
158  struct stat st;
159  if (fstat(in_fd, &st) < 0) die("fstat(input) failed");
160  if (!S_ISREG(st.st_mode)) {
161    fprintf(stderr, "input must be a regular file\n");
162    return 2;
163  }
164
165  size_t in_size = (size_t)st.st_size;
166  size_t hpsz = detect_hugepage_size_from_path(out_path);
167  size_t out_size = round_up_size(in_size, hpsz);
168
169  int out_fd = open(out_path, O_RDWR | O_CREAT | O_TRUNC, 0644);
170  if (out_fd < 0) die("open(output) failed");
171
172  if (ftruncate(out_fd, (off_t)out_size) < 0) die("ftruncate(output) failed");
173
174  size_t flags = 0;
175  switch (hpsz) {
176    case (2 * 1024 * 1024): flags = MAP_HUGE_2MB; break;
177    case (1 * 1024 * 1024 * 1024): flags = MAP_HUGE_1GB; break;
178  }
179  void *dst = mmap(NULL, out_size, PROT_READ | PROT_WRITE, MAP_SHARED | MAP_HUGETLB | flags, out_fd, 0);
180  if (dst == MAP_FAILED) die("mmap(output) failed");
181
182  int use_numa = (getenv("NUMA") != NULL);
183  if (!use_numa) {
184    copy_range(in_fd, in_size, dst, 0, out_size);
185  } else {
186    struct numa_node_info *nodes = NULL;
187    int nnodes = 0;
188    long total_weight = 0;
189
190    setup_numa(&nodes, &nnodes, &total_weight);
191    // Compute per-node byte ranges proportional to cpu_count
192    size_t remaining = in_size;
193    size_t offset = 0;
194
195    for (int i = 0; i < nnodes; i++) {
196      struct numa_node_info *ni = &nodes[i];
197
198      // Proportional share
199      size_t share = 0;
200      if (i == nnodes - 1) {
201        // give the remainder to the last node to cover whole file
202        share = remaining;
203      } else {
204        double fraction = (double)ni->cpu_count / (double)total_weight;
205        share = (size_t)((double)in_size * fraction);
206        if (share > remaining) share = remaining;
207      }
208
209      if (share == 0 && i != nnodes - 1) {
210        continue;
211      }
212
213      pid_t pid = fork();
214      if (pid < 0) die("fork failed");
215
216      if (pid == 0) {
217        // Child: pin to this node's CPUs and copy our range
218        if (sched_setaffinity(0, sizeof(cpu_set_t), &ni->cpuset) != 0) {
219          die("sched_setaffinity failed");
220        }
221
222        copy_range(in_fd, in_size, dst, offset, share);
223
224        _exit(0);
225      } else {
226        int status = 0;
227        if (waitpid(pid, &status, 0) < 0) die("waitpid failure");
228        if (!WIFEXITED(status) || WEXITSTATUS(status) != 0) {
229          die("child exited abnormally");
230        }
231      }
232
233      offset += share;
234      if (remaining >= share) remaining -= share;
235      else remaining = 0;
236    }
237
238    free(nodes);
239
240    if (out_size > in_size) {
241      memset((char *)dst + in_size, 0, out_size - in_size);
242    }
243  }
244
245  if (msync(dst, out_size, MS_SYNC) < 0) die("msync failed");
246
247  if (munmap(dst, out_size) < 0) die("munmap failed");
248  if (close(out_fd) < 0) die("close(output) failed");
249  if (close(in_fd) < 0) die("close(input) failed");
250
251  return 0;
252}