2 * Copyright (c) 2014, Facebook, Inc.
5 * This source code is licensed under the BSD-style license found in the
6 * LICENSE file in the "hack" directory of this source tree. An additional grant
7 * of patent rights can be found in the PATENTS file in the same directory.
11 /*****************************************************************************/
12 /* File Implementing the shared memory system for Hack.
14 * THIS CODE ONLY WORKS WITH HACK, IT MAY LOOK LIKE A GENERIC ATOMIC
15 * HASHTABLE FOR OCAML: IT IS NOT!
16 * BUT ... YOU WERE GOING TO SAY BUT? BUT ...
17 * THERE IS NO BUT! DONNY YOU'RE OUT OF YOUR ELEMENT!
19 * The lock-free data structures implemented here only work because of how
20 * the Hack phases are synchronized.
22 * There are 3 kinds of storage implemented in this file.
23 * I) The global storage. Used by the master to efficiently transfer a blob
24 * of data to the workers. This is used to share an environment in
25 * read-only mode with all the workers.
26 * The master stores, the workers read.
28 * II) The dependency table. It's a hashtable that contains all the
29 * dependencies between Hack objects. It is filled concurrently by
33 * The operations implemented, and their limitations:
35 * -) Concurrent writes: SUPPORTED
36 * As long as its not interleaved with any other operation
39 * -) Concurrent reads: SUPPORTED
40 * As long as they are no concurrent writers.
42 * -) Concurrent removes: NOT SUPPORTED
43 * Only the master can remove.
45 /*****************************************************************************/
47 #include <caml/memory.h>
48 #include <caml/alloc.h>
55 #include <sys/types.h>
58 #include <sys/errno.h>
60 #include <sys/resource.h>
62 #include <sys/syscall.h>
64 #define GIG (1024l * 1024l * 1024l)
66 /* Convention: .*_B = Size in bytes. */
68 /* Size of the "global storage". */
69 #define GLOBAL_SIZE_B GIG
71 /* Used for the dependency hashtable */
73 #define DEP_SIZE (1 << DEP_POW)
74 #define DEP_SIZE_B (DEP_SIZE * sizeof(value))
76 /* Used for the shared hashtable */
77 #define HASHTBL_POW 23
78 #define HASHTBL_SIZE (1 << HASHTBL_POW)
79 #define HASHTBL_SIZE_B (HASHTBL_SIZE * sizeof(helt_t))
81 /* Size of where we allocate shared objects. */
82 #define HEAP_SIZE (8 * GIG)
83 #define Get_size(x) (((size_t*)(x))[-1])
84 #define Get_buf_size(x) (((size_t*)(x))[-1] + sizeof(size_t))
85 #define Get_buf(x) (x - sizeof(size_t))
87 /* The total size of the shared memory.
88 * Most of it is going to remain virtual.
90 #define SHARED_MEM_SIZE (GLOBAL_SIZE_B + DEP_SIZE_B + HASHTBL_SIZE_B +\
93 /* Too lazy to use getconf */
94 #define CACHE_LINE_SIZE (1 << 6)
95 #define CACHE_MASK (~(CACHE_LINE_SIZE - 1))
96 #define ALIGNED(x) ((x + CACHE_LINE_SIZE - 1) & CACHE_MASK)
98 /*****************************************************************************/
100 /*****************************************************************************/
102 /* Cells of the Hashtable */
108 /*****************************************************************************/
110 /*****************************************************************************/
112 /* The location of the shared memory */
113 static char* shared_mem
;
115 /* ENCODING: The first element is the size stored in bytes, the rest is
116 * the data. The size is set to zero when the storage is empty.
118 static value
* global_storage
;
121 * The highest 2 bits are unused.
122 * The next 31 bits encode the key the lower 31 bits the value.
124 static uint64_t* deptbl
;
126 /* The hashtable containing the shared values. */
127 static helt_t
* hashtbl
;
128 static int* hcounter
; // the number of slots taken in the table
130 /* A counter increasing globally across all forks. */
131 static uintptr_t* counter
;
132 static uintptr_t early_counter
= 1;
134 /* The top of the heap */
137 /* Useful to add assertions */
138 static pid_t master_pid
;
141 /* Where the heap started (bottom) */
142 static char* heap_init
;
144 /* The size of the heap after initialization of the server */
145 static size_t heap_init_size
= 0;
147 /* The size of a page (memory page) */
148 static int page_size
;
150 /*****************************************************************************/
151 /* Given a pointer to the shared memory address space, initializes all
152 * the globals that live in shared memory.
154 /*****************************************************************************/
155 static void init_shared_globals(char* mem
) {
156 int page_size
= getpagesize();
159 /* We keep all the small objects in the first page.
160 * There are on different cache lines because we modify them atomically.
163 /* BEGINING OF THE FIRST PAGE */
164 /* The pointer to the top of the heap.
165 * We will atomically increment *heap every time we want to allocate.
168 assert(CACHE_LINE_SIZE
>= sizeof(char*));
170 // The number of elements in the hashtable
171 hcounter
= (int*)(mem
+ CACHE_LINE_SIZE
);
174 counter
= (uintptr_t*)(mem
+ 2*CACHE_LINE_SIZE
);
175 *counter
= early_counter
+ 1;
178 // Just checking that the page is large enough.
179 assert(page_size
> CACHE_LINE_SIZE
+ sizeof(int));
180 /* END OF THE FIRST PAGE */
182 /* Global storage initialization */
183 global_storage
= (value
*)mem
;
184 // Initial size is zero
185 global_storage
[0] = 0;
186 mem
+= GLOBAL_SIZE_B
;
189 deptbl
= (uint64_t*)mem
;
193 hashtbl
= (helt_t
*)mem
;
194 mem
+= HASHTBL_SIZE_B
;
200 // Checking that we did the maths correctly.
201 assert(mem
+ HEAP_SIZE
== bottom
+ SHARED_MEM_SIZE
+ page_size
);
204 /*****************************************************************************/
205 /* Sets CPU and IO priorities. */
206 /*****************************************************************************/
208 // glibc refused to add ioprio_set, sigh.
209 // https://sourceware.org/bugzilla/show_bug.cgi?id=4464
210 #define IOPRIO_CLASS_SHIFT 13
211 #define IOPRIO_PRIO_VALUE(cl, dat) (((cl) << IOPRIO_CLASS_SHIFT) | (dat))
212 #define IOPRIO_WHO_PROCESS 1
213 #define IOPRIO_CLASS_IDLE 3
215 static void set_priorities() {
216 // Downgrade to lowest IO priority. We fork a process for each CPU, which
217 // during parsing can slam the disk so hard that the system becomes
218 // unresponsive. While it's unclear why the Linux IO scheduler can't deal with
219 // this better, increasing our startup time in return for a usable system
220 // while we start up is the right tradeoff. (Especially in Facebook's
221 // configuration, where hh_server is often started up in the background well
222 // before the user needs hh_client, so our startup time often doesn't matter
225 // No need to check the return value, if we failed then whatever.
231 IOPRIO_PRIO_VALUE(IOPRIO_CLASS_IDLE
, 7)
235 // Don't slam the CPU either, though this has much less tendency to make the
236 // system totally unresponsive so we don't need to lower all the way.
240 /*****************************************************************************/
241 /* Must be called by the master BEFORE forking the workers! */
242 /*****************************************************************************/
243 void hh_shared_init() {
244 /* MAP_NORESERVE is because we want a lot more virtual memory than what
245 * we are actually going to use.
247 int flags
= MAP_SHARED
| MAP_ANON
| MAP_NORESERVE
;
248 int prot
= PROT_READ
| PROT_WRITE
;
250 page_size
= getpagesize();
253 (char*)mmap(NULL
, page_size
+ SHARED_MEM_SIZE
, prot
, flags
, 0, 0);
255 if(shared_mem
== MAP_FAILED
) {
256 printf("Error initializing: %s\n", strerror(errno
));
260 // Keeping the pids around to make asserts.
261 master_pid
= getpid();
264 init_shared_globals(shared_mem
);
266 // Uninstall ocaml's segfault handler. It's supposed to throw an exception on
267 // stack overflow, but we don't actually handle that exception, so what
268 // happens in practice is we terminate at toplevel with an unhandled exception
269 // and a useless ocaml backtrace. A core dump is actually more useful. Sigh.
270 struct sigaction sigact
= {};
271 sigact
.sa_handler
= SIG_DFL
;
272 sigemptyset(&sigact
.sa_mask
);
274 sigaction(SIGSEGV
, &sigact
, NULL
);
279 /* Must be called by every worker before any operation is performed */
280 void hh_worker_init() {
284 /*****************************************************************************/
287 * Provides a counter intended to be increasing over the lifetime of the program
288 * including all forks. Uses a global variable until hh_shared_init is called,
289 * so it's safe to use in the early init stages of the program (as long as you
290 * fork after hh_shared_init of course). Wraps around at the maximum value of an
291 * ocaml int, which is something like 30 or 62 bits on 32 and 64-bit
292 * architectures respectively.
294 /*****************************************************************************/
296 value
hh_counter_next() {
302 v
= __sync_fetch_and_add(counter
, 1);
307 result
= Val_long(v
% Max_long
); // Wrap around.
311 /*****************************************************************************/
313 /*****************************************************************************/
315 void hh_shared_store(value data
) {
316 size_t size
= caml_string_length(data
);
318 assert(my_pid
== master_pid
); // only the master can store
319 assert(global_storage
[0] == 0); // Is it clear?
320 assert(size
< GLOBAL_SIZE_B
- sizeof(value
)); // Do we have enough space?
322 global_storage
[0] = size
;
323 memcpy(&global_storage
[1], &Field(data
, 0), size
);
326 /*****************************************************************************/
327 /* We are allocating ocaml values. The OCaml GC must know about them.
328 * caml_alloc_string might trigger the GC, when that happens, the GC needs
329 * to scan the stack to find the OCaml roots. The macros CAMLparam0 and
330 * CAMLlocal1 register the roots.
332 /*****************************************************************************/
334 value
hh_shared_load() {
338 size_t size
= global_storage
[0];
340 result
= caml_alloc_string(size
);
341 memcpy(&Field(result
, 0), &global_storage
[1], size
);
346 void hh_shared_clear() {
347 assert(my_pid
== master_pid
);
348 global_storage
[0] = 0;
351 /*****************************************************************************/
353 /*****************************************************************************/
354 /* This code is very perf sensitive, please check the performance before
356 * The table contains key/value bindings encoded in a word.
357 * The higher bits represent the key, the lower ones the value.
358 * Each key/value binding is unique, but a key can have multiple value
360 * Concretely, if you try to add a key/value pair that is already in the table
361 * the data structure is left unmodified.
362 * If you try to add a key bound to a new value, the binding is added, the
363 * old binding is not removed.
365 /*****************************************************************************/
367 void hh_add_dep(value ocaml_dep
) {
368 unsigned long dep
= Long_val(ocaml_dep
);
369 unsigned long hash
= dep
>> 31;
370 unsigned long slot
= hash
& (DEP_SIZE
- 1);
373 /* It considerably speeds things up to do a normal load before trying using
374 * an atomic operation.
376 uint64_t slot_val
= deptbl
[slot
];
378 // The binding exists, done!
382 // The slot is free, let's try to take it.
384 // See comments in hh_add about its similar construction here.
385 if(__sync_bool_compare_and_swap(&deptbl
[slot
], 0, dep
)) {
389 if(deptbl
[slot
] == dep
) {
394 slot
= (slot
+ 1) & (DEP_SIZE
- 1);
398 /* Given a key, returns the list of values bound to it. */
399 value
hh_get_dep(value dep
) {
401 CAMLlocal2(result
, cell
);
403 unsigned long hash
= Long_val(dep
);
404 unsigned long slot
= hash
& (DEP_SIZE
- 1);
406 result
= Val_int(0); // The empty list
409 if(deptbl
[slot
] == 0) {
412 if(deptbl
[slot
] >> 31 == hash
) {
413 cell
= caml_alloc_tuple(2);
414 Field(cell
, 0) = Val_long(deptbl
[slot
] & ((1l << 31) - 1));
415 Field(cell
, 1) = result
;
418 slot
= (slot
+ 1) & (DEP_SIZE
- 1);
424 /*****************************************************************************/
425 /* Garbage collector */
426 /*****************************************************************************/
428 /*****************************************************************************/
429 /* Must be called after the hack server is done initializing.
430 * We keep the original size of the heap to estimate how often we should
433 /*****************************************************************************/
434 void hh_call_after_init() {
435 heap_init_size
= (uintptr_t)*heap
- (uintptr_t)heap_init
;
438 /*****************************************************************************/
439 /* We compact the heap when it gets twice as large as its initial size.
440 * Step one, copy the live values in a new heap.
441 * Step two, memcopy the values back into the shared heap.
442 * We could probably use something smarter, but this is fast enough.
444 * The collector should only be called by the master.
446 /*****************************************************************************/
448 int flags
= MAP_PRIVATE
| MAP_ANON
| MAP_NORESERVE
;
449 int prot
= PROT_READ
| PROT_WRITE
;
454 assert(heap_init_size
>= 0);
456 if(*heap
< heap_init
+ 2 * heap_init_size
) {
457 // We have not grown passed twice the size of the initial size
461 tmp_heap
= (char*)mmap(NULL
, HEAP_SIZE
, prot
, flags
, 0, 0);
464 if(tmp_heap
== MAP_FAILED
) {
465 printf("Error while collecting: %s\n", strerror(errno
));
469 assert(my_pid
== master_pid
); // Comes from the master
473 for(i
= 0; i
< HASHTBL_SIZE
; i
++) {
474 if(hashtbl
[i
].addr
!= NULL
) { // Found a non empty slot
475 size_t bl_size
= Get_buf_size(hashtbl
[i
].addr
);
476 size_t aligned_size
= ALIGNED(bl_size
);
477 char* addr
= Get_buf(hashtbl
[i
].addr
);
479 memcpy(dest
, addr
, bl_size
);
480 // This is where the data ends up after the copy
481 hashtbl
[i
].addr
= heap_init
+ mem_size
+ sizeof(size_t);
482 dest
+= aligned_size
;
483 mem_size
+= aligned_size
;
487 // Copying the result back into shared memory
488 memcpy(heap_init
, tmp_heap
, mem_size
);
489 *heap
= heap_init
+ mem_size
;
491 if(munmap(tmp_heap
, HEAP_SIZE
) == -1) {
492 printf("Error while collecting: %s\n", strerror(errno
));
497 /*****************************************************************************/
498 /* Allocates in the shared heap.
499 * The chunks are cache aligned.
500 * The word before the chunk address contains the size of the chunk in bytes.
501 * The function returns a pointer to the data (the size can be accessed by
502 * looking at the address: chunk - sizeof(size_t)).
504 /*****************************************************************************/
506 static char* hh_alloc(size_t size
) {
507 size_t slot_size
= ALIGNED(size
+ sizeof(size_t));
508 char* chunk
= __sync_fetch_and_add(heap
, slot_size
);
509 *((size_t*)chunk
) = size
;
510 return (chunk
+ sizeof(size_t));
513 /*****************************************************************************/
514 /* Allocates an ocaml value in the shared heap.
515 * The values can only be ocaml strings. It returns the address of the
518 /*****************************************************************************/
519 static char* hh_store_ocaml(value data
) {
520 size_t data_size
= caml_string_length(data
);
521 char* addr
= hh_alloc(data_size
);
522 memcpy(addr
, String_val(data
), data_size
);
526 /*****************************************************************************/
527 /* Given an OCaml string, returns the 8 first bytes in an unsigned long.
528 * The key is generated using MD5, but we only use the first 8 bytes because
529 * it allows us to use atomic operations.
531 /*****************************************************************************/
532 static unsigned long get_hash(value key
) {
533 return *((unsigned long*)String_val(key
));
536 /*****************************************************************************/
537 /* Writes the data in one of the slots of the hashtable. There might be
538 * concurrent writers, when that happens, the first writer wins.
540 /*****************************************************************************/
541 static void write_at(unsigned int slot
, value data
) {
542 if(hashtbl
[slot
].addr
== NULL
&&
543 __sync_bool_compare_and_swap(&(hashtbl
[slot
].addr
), NULL
, 1)) {
544 hashtbl
[slot
].addr
= hh_store_ocaml(data
);
548 /*****************************************************************************/
549 /* Adds a key value to the hashtable. This code is perf sensitive, please
550 * check the perf before modifying.
552 /*****************************************************************************/
553 void hh_add(value key
, value data
) {
554 unsigned long hash
= get_hash(key
);
555 unsigned int slot
= hash
& (HASHTBL_SIZE
- 1);
558 unsigned long slot_hash
= hashtbl
[slot
].hash
;
560 if(slot_hash
== hash
) {
561 write_at(slot
, data
);
566 // We think we might have a free slot, try to atomically grab it.
567 if(__sync_bool_compare_and_swap(&(hashtbl
[slot
].hash
), 0, hash
)) {
568 unsigned long size
= __sync_fetch_and_add(hcounter
, 1);
569 assert(size
< HASHTBL_SIZE
);
570 write_at(slot
, data
);
574 // Grabbing it failed -- why? If someone else inserted the data we were
575 // about to, we are done (don't double-insert). Otherwise, keep going.
576 // Note that this read relies on the __sync call above preventing the
577 // compiler from caching the value read out of memory. (And of course
578 // isn't safe on any arch that requires memory barriers.)
579 if(hashtbl
[slot
].hash
== hash
) {
580 // FIXME: there is a race here. The data may not actually be written by
581 // the time we return here, and even the sigil value "1" may not be
582 // written into the address by the winning thread. If this thread
583 // manages to call hh_mem on this key before the winning thread can
584 // write the sigil "1", things will be broken since the data we just
585 // wrote will be missing. Want to more carefully think out the right
586 // fix and need to commit a fix for a much worse race, so leaving this
587 // here for now -- this thread has to get all the way back into hh_mem
588 // before the other thread executes the 37 instructions it takes to
589 // write the sigil, so I'm not super worried.
594 slot
= (slot
+ 1) & (HASHTBL_SIZE
- 1);
598 /*****************************************************************************/
599 /* Finds the slot corresponding to the key in a hash table. The returned slot
600 * is either free or points to the key.
602 /*****************************************************************************/
603 static unsigned int find_slot(value key
) {
604 unsigned long hash
= get_hash(key
);
605 unsigned int slot
= hash
& (HASHTBL_SIZE
- 1);
608 if(hashtbl
[slot
].hash
== hash
) {
611 if(hashtbl
[slot
].hash
== 0) {
614 slot
= (slot
+ 1) & (HASHTBL_SIZE
- 1);
618 /*****************************************************************************/
619 /* Returns true if the key is present. We need to check both the hash and
620 * the address of the data. This is due to the fact that we remove by setting
621 * the address slot to NULL (we never remove a hash from the table, outside
622 * of garbage collection).
624 /*****************************************************************************/
625 value
hh_mem(value key
) {
626 unsigned int slot
= find_slot(key
);
627 if(hashtbl
[slot
].hash
== get_hash(key
) &&
628 hashtbl
[slot
].addr
!= NULL
) {
629 // The data is currently in the process of being written, wait until it
630 // actually is ready to be used before returning.
631 while (hashtbl
[slot
].addr
== (char*)1) {
632 asm volatile("pause" : : : "memory");
639 /*****************************************************************************/
640 /* Returns the value associated to a given key. The key MUST be present. */
641 /*****************************************************************************/
642 value
hh_get(value key
) {
646 unsigned int slot
= find_slot(key
);
647 assert(hashtbl
[slot
].hash
== get_hash(key
));
648 size_t size
= *(size_t*)(hashtbl
[slot
].addr
- sizeof(size_t));
649 result
= caml_alloc_string(size
);
650 memcpy(String_val(result
), hashtbl
[slot
].addr
, size
);
655 /*****************************************************************************/
656 /* Moves the data associated to key1 to key2.
657 * key1 must be present.
659 * Only the master can perform this operation.
661 /*****************************************************************************/
662 void hh_move(value key1
, value key2
) {
663 unsigned int slot1
= find_slot(key1
);
664 unsigned int slot2
= find_slot(key2
);
666 assert(my_pid
== master_pid
);
667 assert(hashtbl
[slot1
].hash
== get_hash(key1
));
668 assert(hashtbl
[slot2
].addr
== NULL
);
669 hashtbl
[slot2
].hash
= get_hash(key2
);
670 hashtbl
[slot2
].addr
= hashtbl
[slot1
].addr
;
671 hashtbl
[slot1
].addr
= NULL
;
674 /*****************************************************************************/
675 /* Removes a key from the hash table.
676 * Only the master can perform this operation.
678 /*****************************************************************************/
679 void hh_remove(value key
) {
680 unsigned int slot
= find_slot(key
);
682 assert(my_pid
== master_pid
);
683 assert(hashtbl
[slot
].hash
== get_hash(key
));
684 hashtbl
[slot
].addr
= NULL
;
687 /*****************************************************************************/
688 /* Returns a copy of the content of a file in an ocaml string.
689 * This code should be very tolerant to failure. At any given time, the
690 * file could be modified, when that happens, we don't want to fail, we
691 * return the empty string instead.
693 /*****************************************************************************/
695 value
hh_read_file(value filename
) {
696 CAMLparam1(filename
);
703 fd
= open(String_val(filename
), O_RDONLY
);
705 result
= caml_alloc_string(0);
707 else if(fstat(fd
, &sb
) == -1) {
708 result
= caml_alloc_string(0);
712 (char*)mmap(NULL
, sb
.st_size
, PROT_READ
, MAP_PRIVATE
, fd
, 0))
714 result
= caml_alloc_string(0);
718 result
= caml_alloc_string(sb
.st_size
);
719 memcpy(String_val(result
), memblock
, sb
.st_size
);
720 munmap(memblock
, sb
.st_size
);