aboutsummaryrefslogtreecommitdiffstats
path: root/erts/emulator/beam/erl_db_util.h
blob: 1a84f20e5d58cc0697248abc5b1fcdc8175ac777 (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
/*
 * %CopyrightBegin%
 *
 * Copyright Ericsson AB 1998-2016. All Rights Reserved.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 *
 * %CopyrightEnd%
 */

#ifndef _DB_UTIL_H
#define _DB_UTIL_H

#include "global.h"
#include "erl_message.h"
#include "erl_bif_unique.h"

/*#define HARDDEBUG 1*/

#ifdef DEBUG
/*
** DMC_DEBUG does NOT need DEBUG, but DEBUG needs DMC_DEBUG
*/
#define DMC_DEBUG 1
#endif

/*
 * These values can be returned from the functions performing the 
 * BIF operation for different types of tables. When the
 * actual operations have been performed, the BIF function
 * checks for negative returns and issues BIF_ERRORS based 
 * upon these values.
 */
#define DB_ERROR_NONE      0     /* No error */
#define DB_ERROR_BADITEM  -1     /* The item was malformed ie no 
				   tuple or to small*/
#define DB_ERROR_BADTABLE -2     /* The Table is inconsisitent */
#define DB_ERROR_SYSRES   -3     /* Out of system resources */
#define DB_ERROR_BADKEY   -4     /* Returned if a key that should
				    exist does not. */
#define DB_ERROR_BADPARAM  -5     /* Returned if a specified slot does 
				     not exist (hash table only) or
				     the state parameter in db_match_object
				     is broken.*/
#define DB_ERROR_UNSPEC   -10    /* Unspecified error */

/*#define DEBUG_CLONE*/

/*
 * A datatype for a database entry stored out of a process heap
 */
typedef struct db_term {
    struct erl_off_heap_header* first_oh; /* Off heap data for term. */
    Uint size;		   /* Heap size of term in "words" */
#ifdef DEBUG_CLONE
    Eterm* debug_clone;    /* An uncompressed copy */
#endif
    Eterm tpl[1];          /* Term data. Top tuple always first */

    /* Compression: is_immed and key element are uncompressed.
       Compressed elements are stored in external format after each other
       last in dbterm. The top tuple elements contains byte offsets, to
       the start of the data, tagged as headers.
       The allocated size of the dbterm in bytes is stored at tpl[arity+1].
     */
} DbTerm;

#define DB_MUST_RESIZE 1
#define DB_NEW_OBJECT 2
#define DB_INC_TRY_GROW 4

/* Info about a database entry while it's being updated
 * (by update_counter or update_element)
 */
typedef struct {
    DbTable* tb;
    DbTerm* dbterm;
    void** bp;         /* {Hash|Tree}DbTerm** */
    Uint new_size;
    int flags;
    void* lck;
} DbUpdateHandle;


typedef struct db_table_method
{
    int (*db_create)(Process *p, DbTable* tb);
    int (*db_first)(Process* p, 
		    DbTable* tb, /* [in out] */ 
		    Eterm* ret   /* [out] */);
    int (*db_next)(Process* p, 
		   DbTable* tb, /* [in out] */
		   Eterm key,   /* [in] */
		   Eterm* ret /* [out] */);
    int (*db_last)(Process* p, 
		   DbTable* tb, /* [in out] */
		   Eterm* ret   /* [out] */);
    int (*db_prev)(Process* p, 
		   DbTable* tb, /* [in out] */
		   Eterm key, 
		   Eterm* ret);
    int (*db_put)(DbTable* tb, /* [in out] */ 
		  Eterm obj,
		  int key_clash_fail); /* DB_ERROR_BADKEY if key exists */ 
    int (*db_get)(Process* p, 
		  DbTable* tb, /* [in out] */ 
		  Eterm key, 
		  Eterm* ret);
    int (*db_get_element)(Process* p, 
			  DbTable* tb, /* [in out] */ 
			  Eterm key, 
			  int index, 
			  Eterm* ret);
    int (*db_member)(DbTable* tb, /* [in out] */ 
		     Eterm key, 
		     Eterm* ret);
    int (*db_erase)(DbTable* tb,  /* [in out] */ 
		    Eterm key, 
		    Eterm* ret);
    int (*db_erase_object)(DbTable* tb, /* [in out] */ 
			   Eterm obj,
			   Eterm* ret);
    int (*db_slot)(Process* p, 
		   DbTable* tb, /* [in out] */ 
		   Eterm slot, 
		   Eterm* ret);
    int (*db_select_chunk)(Process* p, 
			   DbTable* tb, /* [in out] */
                           Eterm tid,
			   Eterm pattern,
			   Sint chunk_size,
			   int reverse,
			   Eterm* ret);
    int (*db_select)(Process* p, 
		     DbTable* tb, /* [in out] */
                     Eterm tid,
		     Eterm pattern,
		     int reverse,
		     Eterm* ret);
    int (*db_select_delete)(Process* p, 
			    DbTable* tb, /* [in out] */
                            Eterm tid,
			    Eterm pattern,
			    Eterm* ret);
    int (*db_select_continue)(Process* p, 
			      DbTable* tb, /* [in out] */
			      Eterm continuation,
			      Eterm* ret);
    int (*db_select_delete_continue)(Process* p, 
				     DbTable* tb, /* [in out] */
				     Eterm continuation,
				     Eterm* ret);
    int (*db_select_count)(Process* p, 
			   DbTable* tb, /* [in out] */
                           Eterm tid,
			   Eterm pattern, 
			   Eterm* ret);
    int (*db_select_count_continue)(Process* p, 
				    DbTable* tb, /* [in out] */ 
				    Eterm continuation, 
				    Eterm* ret);
    int (*db_select_replace)(Process* p,
            DbTable* tb, /* [in out] */
            Eterm pattern,
            Eterm* ret);
    int (*db_select_replace_continue)(Process* p,
            DbTable* tb, /* [in out] */
            Eterm continuation,
            Eterm* ret);
    int (*db_take)(Process *, DbTable *, Eterm, Eterm *);

    int (*db_delete_all_objects)(Process* p,
				 DbTable* db /* [in out] */ );

    int (*db_free_table)(DbTable* db /* [in out] */ );
    SWord (*db_free_table_continue)(DbTable* db, SWord reds);
    
    void (*db_print)(fmtfn_t to,
		     void* to_arg, 
		     int show, 
		     DbTable* tb /* [in out] */ );

    void (*db_foreach_offheap)(DbTable* db,  /* [in out] */ 
			       void (*func)(ErlOffHeap *, void *),
			       void *arg);

    /* Lookup a dbterm for updating. Return false if not found. */
    int (*db_lookup_dbterm)(Process *, DbTable *, Eterm key, Eterm obj,
                            DbUpdateHandle* handle);

    /* Must be called for each db_lookup_dbterm that returned true, even if
    ** dbterm was not updated. If the handle was of a new object and cret is
    ** not DB_ERROR_NONE, the object is removed from the table. */
    void (*db_finalize_dbterm)(int cret, DbUpdateHandle* handle);

} DbTableMethod;

typedef struct db_fixation {
    /* Node in fixed_tabs list */
    struct {
        struct db_fixation *next, *prev;
        Binary* btid;
    } tabs;

    /* Node in fixing_procs tree */
    struct {
        struct db_fixation *left, *right, *parent;
        int is_red;
        Process* p;
    } procs;

    Uint counter;
} DbFixation;

typedef struct {
    DbTable *next;
    DbTable *prev;
} DbTableList;

/*
 * This structure contains data for all different types of database
 * tables. Note that these fields must match the same fields
 * in the table-type specific structures.
 * The reason it is placed here and not in db.h is that some table 
 * operations may be the same on different types of tables.
 */

typedef struct db_table_common {
    erts_smp_refc_t refc;     /* reference count of table struct */
    erts_smp_refc_t fix_count;/* fixation counter */
    DbTableList all;
    DbTableList owned;
#ifdef ERTS_SMP
    erts_smp_rwmtx_t rwlock;  /* rw lock on table */
    erts_smp_mtx_t fixlock;   /* Protects fixing_procs and time */
    int is_thread_safe;       /* No fine locking inside table needed */
    Uint32 type;              /* table type, *read only* after creation */
#endif
    Eterm owner;              /* Pid of the creator */
    Eterm heir;               /* Pid of the heir */
    UWord heir_data;          /* To send in ETS-TRANSFER (is_immed or (DbTerm*) */
    Uint64 heir_started_interval;  /* To further identify the heir */
    Eterm the_name;           /* an atom */
    Binary *btid;
    DbTableMethod* meth;      /* table methods */
    erts_smp_atomic_t nitems; /* Total number of items in table */
    erts_smp_atomic_t memory_size;/* Total memory size. NOTE: in bytes! */
    struct {                  /* Last fixation time */
	ErtsMonotonicTime monotonic;
	ErtsMonotonicTime offset;
    } time;
    DbFixation* fixing_procs; /* Tree of processes who have done safe_fixtable,
                                 "local" fixations not included. */ 
    /* All 32-bit fields */
    Uint32 status;            /* bit masks defined  below */
    int keypos;               /* defaults to 1 */
    int compress;
} DbTableCommon;

/* These are status bit patterns */
#define DB_PRIVATE       (1 << 0)
#define DB_PROTECTED     (1 << 1)
#define DB_PUBLIC        (1 << 2)
#define DB_DELETE        (1 << 3) /* table is being deleted */
#define DB_SET           (1 << 4)
#define DB_BAG           (1 << 5)
#define DB_DUPLICATE_BAG (1 << 6)
#define DB_ORDERED_SET   (1 << 7)
#define DB_FINE_LOCKED   (1 << 8) /* write_concurrency */
#define DB_FREQ_READ     (1 << 9) /* read_concurrency */
#define DB_NAMED_TABLE   (1 << 10)

#define ERTS_ETS_TABLE_TYPES (DB_BAG|DB_SET|DB_DUPLICATE_BAG|DB_ORDERED_SET\
                              |DB_FINE_LOCKED|DB_FREQ_READ|DB_NAMED_TABLE)

#define IS_HASH_TABLE(Status) (!!((Status) & \
				  (DB_BAG | DB_SET | DB_DUPLICATE_BAG)))
#define IS_TREE_TABLE(Status) (!!((Status) & \
				  DB_ORDERED_SET))
#define NFIXED(T) (erts_smp_refc_read(&(T)->common.fix_count,0))
#define IS_FIXED(T) (NFIXED(T) != 0) 

/*
 * tplp is an untagged pointer to a tuple we know is large enough
 * and dth is a pointer to a DbTableHash.
 */
#define GETKEY(dth, tplp)   (*((tplp) + ((DbTableCommon*)(dth))->keypos))


ERTS_GLB_INLINE Eterm db_copy_key(Process* p, DbTable* tb, DbTerm* obj);
Eterm db_copy_from_comp(DbTableCommon* tb, DbTerm* bp, Eterm** hpp,
			ErlOffHeap* off_heap);
int db_eq_comp(DbTableCommon* tb, Eterm a, DbTerm* b);
DbTerm* db_alloc_tmp_uncompressed(DbTableCommon* tb, DbTerm* org);

ERTS_GLB_INLINE Eterm db_copy_object_from_ets(DbTableCommon* tb, DbTerm* bp,
					      Eterm** hpp, ErlOffHeap* off_heap);
ERTS_GLB_INLINE int db_eq(DbTableCommon* tb, Eterm a, DbTerm* b);
Wterm db_do_read_element(DbUpdateHandle* handle, Sint position);

#if ERTS_GLB_INLINE_INCL_FUNC_DEF

ERTS_GLB_INLINE Eterm db_copy_key(Process* p, DbTable* tb, DbTerm* obj)
{
    Eterm key = GETKEY(tb, obj->tpl);
    if IS_CONST(key) return key;
    else {
	Uint size = size_object(key);
	Eterm* hp = HAlloc(p, size);
	Eterm res = copy_struct(key, size, &hp, &MSO(p));
	ASSERT(EQ(res,key));
	return res;
    }
}

ERTS_GLB_INLINE Eterm db_copy_object_from_ets(DbTableCommon* tb, DbTerm* bp,
					      Eterm** hpp, ErlOffHeap* off_heap)
{
    if (tb->compress) {
	return db_copy_from_comp(tb, bp, hpp, off_heap);
    }
    else {
	return copy_shallow(bp->tpl, bp->size, hpp, off_heap);
    }
}

ERTS_GLB_INLINE int db_eq(DbTableCommon* tb, Eterm a, DbTerm* b)
{
    if (!tb->compress) {
	return EQ(a, make_tuple(b->tpl));
    }
    else {
	return db_eq_comp(tb, a, b);
    }
}

#endif /* ERTS_GLB_INLINE_INCL_FUNC_DEF */


#define DB_READ  (DB_PROTECTED|DB_PUBLIC)
#define DB_WRITE DB_PUBLIC
#define DB_INFO  (DB_PROTECTED|DB_PUBLIC|DB_PRIVATE)

#define ONLY_WRITER(P,T) (((T)->common.status & (DB_PRIVATE|DB_PROTECTED)) \
			  && (T)->common.owner == (P)->common.id)

#define ONLY_READER(P,T) (((T)->common.status & DB_PRIVATE) && \
(T)->common.owner == (P)->common.id)

/* Function prototypes */
BIF_RETTYPE db_get_trace_control_word(Process* p);
BIF_RETTYPE db_set_trace_control_word(Process* p, Eterm tcw);
BIF_RETTYPE db_get_trace_control_word_0(BIF_ALIST_0);
BIF_RETTYPE db_set_trace_control_word_1(BIF_ALIST_1);

void db_initialize_util(void);
Eterm db_getkey(int keypos, Eterm obj);
void db_cleanup_offheap_comp(DbTerm* p);
void db_free_term(DbTable *tb, void* basep, Uint offset);
void* db_store_term(DbTableCommon *tb, DbTerm* old, Uint offset, Eterm obj);
void* db_store_term_comp(DbTableCommon *tb, DbTerm* old, Uint offset, Eterm obj);
Eterm db_copy_element_from_ets(DbTableCommon* tb, Process* p, DbTerm* obj,
			       Uint pos, Eterm** hpp, Uint extra);
int db_has_map(Eterm obj);
int db_has_variable(Eterm obj);
int db_is_variable(Eterm obj);
void db_do_update_element(DbUpdateHandle* handle,
			  Sint position,
			  Eterm newval);
void db_finalize_resize(DbUpdateHandle* handle, Uint offset);
Eterm db_add_counter(Eterm** hpp, Wterm counter, Eterm incr);
Eterm db_match_set_lint(Process *p, Eterm matchexpr, Uint flags);
Binary *db_match_set_compile(Process *p, Eterm matchexpr, 
			     Uint flags);
int db_match_keeps_key(int keypos, Eterm match, Eterm guard, Eterm body);
int erts_db_match_prog_destructor(Binary *);

typedef struct match_prog {
    ErlHeapFragment *term_save; /* Only if needed, a list of message 
				    buffers for off heap copies 
				    (i.e. binaries)*/
    int single_variable;     /* ets:match needs to know this. */
    int num_bindings;        /* Size of heap */
    /* The following two are only filled in when match specs 
       are used for tracing */
    struct erl_heap_fragment *saved_program_buf;
    Eterm saved_program;
    Uint heap_size;          /* size of: heap + eheap + stack */
    Uint stack_offset;
#ifdef DMC_DEBUG
    UWord* prog_end;		/* End of program */
#endif
    UWord text[1];		/* Beginning of program */
} MatchProg;

/*
 * The heap-eheap-stack block of a MatchProg is nowadays allocated
 * when the match program is run.
 * - heap: variable bindings
 * - eheap: erlang heap storage
 * - eheap: a "large enough" stack
 */

#define DMC_ERR_STR_LEN 100

typedef enum { dmcWarning, dmcError} DMCErrorSeverity;

typedef struct dmc_error {
    char error_string[DMC_ERR_STR_LEN + 1]; /* printf format string
					       with %d for the variable
					       number (if applicable) */
    int variable;                           /* -1 if no variable is referenced
					       in error string */
    struct dmc_error *next;
    DMCErrorSeverity severity;              /* Error or warning */
} DMCError;

typedef struct dmc_err_info {
    unsigned int *var_trans; /* Translations of variable names, 
				initiated to NULL
				and free'd with sys_free if != NULL 
				after compilation */
    int num_trans;
    int error_added;         /* indicates if the error list contains
				any fatal errors (dmcError severity) */
    DMCError *first;         /* List of errors */
} DMCErrInfo;

/*
** Compilation flags
**
** The dialect is in the 3 least significant bits and are to be interspaced by
** by at least 2 (decimal), thats why ((Uint) 2) isn't used. This is to be 
** able to add DBIF_GUARD or DBIF BODY to it to use in the match_spec bif
** table. The rest of the word is used like ordinary flags, one bit for each 
** flag. Note that DCOMP_TABLE and DCOMP_TRACE are mutually exclusive.
*/
#define DCOMP_TABLE ((Uint) 1) /* Ets and dets. The body returns a value, 
		       * and the parameter to the execution is a tuple. */
#define DCOMP_TRACE ((Uint) 4) /* Trace. More functions are allowed, and the 
		       * parameter to the execution will be an array. */
#define DCOMP_DIALECT_MASK ((Uint) 0x7) /* To mask out the bits marking 
					   dialect */
#define DCOMP_FAKE_DESTRUCTIVE ((Uint) 8) /* When this is active, no setting of
					     trace control words or seq_trace tokens will be done. */

/* Allow lock seizing operations on the tracee and 3rd party processes */
#define DCOMP_ALLOW_TRACE_OPS ((Uint) 0x10)

/* This is call trace */
#define DCOMP_CALL_TRACE ((Uint) 0x20)

Binary *db_match_compile(Eterm *matchexpr, Eterm *guards,
			 Eterm *body, int num_matches, 
			 Uint flags, 
			 DMCErrInfo *err_info);
/* Returns newly allocated MatchProg binary with refc == 0*/

Eterm db_match_dbterm(DbTableCommon* tb, Process* c_p, Binary* bprog,
		      int all, DbTerm* obj, Eterm** hpp, Uint extra);

Eterm db_prog_match(Process *p, Process *self,
                    Binary *prog, Eterm term,
		    Eterm *termp, int arity,
		    enum erts_pam_run_flags in_flags,
		    Uint32 *return_flags /* Zeroed on enter */);

/* returns DB_ERROR_NONE if matches, 1 if not matches and some db error on 
   error. */
DMCErrInfo *db_new_dmc_err_info(void);
/* Returns allocated error info, where errors are collected for lint. */
Eterm db_format_dmc_err_info(Process *p, DMCErrInfo *ei);
/* Formats an error info structure into a list of tuples. */
void db_free_dmc_err_info(DMCErrInfo *ei);
/* Completely free's an error info structure, including all recorded 
   errors */

ERTS_GLB_INLINE Eterm erts_db_make_match_prog_ref(Process *p, Binary *mp, Eterm **hpp);
ERTS_GLB_INLINE Binary *erts_db_get_match_prog_binary(Eterm term);
ERTS_GLB_INLINE Binary *erts_db_get_match_prog_binary_unchecked(Eterm term);

#if ERTS_GLB_INLINE_INCL_FUNC_DEF

/*
 * Convert a match program to a "magic" ref to return up to erlang
 */
ERTS_GLB_INLINE Eterm erts_db_make_match_prog_ref(Process *p, Binary *mp, Eterm **hpp)
{
    return erts_mk_magic_ref(hpp, &MSO(p), mp);
}

ERTS_GLB_INLINE Binary *
erts_db_get_match_prog_binary_unchecked(Eterm term)
{
    Binary *bp = erts_magic_ref2bin(term);
    ASSERT(bp->flags & BIN_FLAG_MAGIC);
    ASSERT((ERTS_MAGIC_BIN_DESTRUCTOR(bp) == erts_db_match_prog_destructor));
    return bp;
}

ERTS_GLB_INLINE Binary *
erts_db_get_match_prog_binary(Eterm term)
{
    Binary *bp;
    if (!is_internal_magic_ref(term))
	return NULL;
    bp = erts_magic_ref2bin(term);
    ASSERT(bp->flags & BIN_FLAG_MAGIC);
    if (ERTS_MAGIC_BIN_DESTRUCTOR(bp) != erts_db_match_prog_destructor)
	return NULL;
    return bp;
}

#endif

/*
** Convenience when compiling into Binary structures
*/
#define IsMatchProgBinary(BP) \
  (((BP)->flags & BIN_FLAG_MAGIC) \
   && ERTS_MAGIC_BIN_DESTRUCTOR((BP)) == erts_db_match_prog_destructor)

#define Binary2MatchProg(BP) \
  (ASSERT(IsMatchProgBinary((BP))), \
   ((MatchProg *) ERTS_MAGIC_BIN_DATA((BP))))

#endif /* _DB_UTIL_H */