Debian Codegraph @

tools/xenstored/transaction.c

raw
1 /*
2 Transaction code for Xen Store Daemon.
3 Copyright (C) 2005 Rusty Russell IBM Corporation
4
5 This program is free software; you can redistribute it and/or modify
6 it under the terms of the GNU General Public License as published by
7 the Free Software Foundation; either version 2 of the License, or
8 (at your option) any later version.
9
10 This program is distributed in the hope that it will be useful,
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 GNU General Public License for more details.
14
15 You should have received a copy of the GNU General Public License
16 along with this program; If not, see <http://www.gnu.org/licenses/>.
17 */
18
19 #include <inttypes.h>
20 #include <stdio.h>
21 #include <sys/types.h>
22 #include <sys/stat.h>
23 #include <sys/wait.h>
24 #include <sys/time.h>
25 #include <time.h>
26 #include <assert.h>
27 #include <stdarg.h>
28 #include <stdlib.h>
29 #include <fcntl.h>
30 #include <unistd.h>
31 #include "talloc.h"
32 #include "list.h"
33 #include "transaction.h"
34 #include "watch.h"
35 #include "domain.h"
36 #include "xenstore_lib.h"
37 #include "utils.h"
38
39 /*
40 * Some notes regarding detection and handling of transaction conflicts:
41 *
42 * Basic source of reference is the 'generation' count. Each writing access
43 * (either normal write or in a transaction) to the tdb data base will set
44 * the node specific generation count to the global generation count.
45 * For being able to identify a transaction the transaction specific generation
46 * count is initialized with the global generation count when starting the
47 * transaction.
48 * Each time the global generation count is copied to either a node or a
49 * transaction it is incremented. This ensures all nodes and/or transactions
50 * are having a unique generation count. The increment is done _before_ the
51 * copy as that is needed for checking whether a domain was created before
52 * or after a node has been written (the domain's generation is set with the
53 * actual generation count without incrementing it, in order to support
54 * writing a node for a domain before the domain has been officially
55 * introduced).
56 *
57 * Transaction conflicts are detected by checking the generation count of all
58 * nodes read in the transaction to match with the generation count in the
59 * global data base at the end of the transaction. Nodes which have been
60 * modified in the transaction don't have to be checked to match even if they
61 * have been read, as the modified node will be globally visible after the
62 * succeeded transaction possibly overwriting another modification which may
63 * have occurred concurrent to the transaction.
64 *
65 * Examples:
66 * ---------
67 * The following notation is used:
68 * I: initial state
69 * G global generation count
70 * g(X) generation count of node X
71 * G(1) generation count of transaction 1
72 * g(1:Y) saved generation count of node Y in transaction 1
73 * TA1: operation in transaction 1
74 * X=1:X replace global node X with transaction 1 specific value of X
75 *
76 * 1. Simple transaction doing: read node A, write node B
77 * I: g(A) = 1, g(B) = 2, G = 3
78 * Start transaction 1: G(1) = 3, G = 4
79 * TA1: read node A: g(1:A) = 1
80 * TA1: write node B: g(1:B) = 4, G = 5
81 * End TA1: g(1:A) == g(A) => okay, B = 1:B, g(B) = 5, G = 6
82 *
83 * 2. Transaction with conflicting write
84 * I: g(A) = 1, g(B) = 2, G = 3
85 * Start transaction 1: G(1) = 3, G = 4
86 * TA1: read node A: g(1:A) = 1
87 * write node A: g(A) = 4, G = 5
88 * TA1: write node B: g(1:B) = 5, G = 6
89 * End TA1: g(1:A) != g(A) => EAGAIN
90 *
91 * 3. Transaction with conflicting delete
92 * I: g(A) = 1, g(B) = 2, G = 3
93 * Start transaction 1: G(1) = 3, G = 4
94 * TA1: read node A: g(1:A) = 1
95 * delete node A: g(A) = ~0
96 * TA1: write node B: g(1:B) = 4, G = 5
97 * End TA1: g(1:A) != g(A) => EAGAIN
98 *
99 * 4. Two interfering transactions
100 * I: g(A) = 1, g(B) = 2, G = 3
101 * Start transaction 1: G(1) = 3, G = 4
102 * Start transaction 2: G(2) = 4, G = 5
103 * TA1: read node A: g(1:A) = 1
104 * TA2: read node B: g(2:B) = 2
105 * TA1: write node B: g(1:B) = 5, G = 6
106 * TA2: write node A: g(2:A) = 6, G = 7
107 * End TA1: g(1:A) == g(A) => okay, B = 1:B, g(B) = 7, G = 8
108 * End TA2: g(2:B) != g(B) => EAGAIN
109 */
110
111 struct accessed_node
112 {
113 /* List of all changed nodes in the context of this transaction. */
114 struct list_head list;
115
116 /* The name of the node. */
117 char *trans_name; /* Transaction specific name. */
118 char *node; /* Main data base name. */
119
120 /* Generation count (or NO_GENERATION) for conflict checking. */
121 uint64_t generation;
122
123 /* Original node permissions. */
124 struct node_perms perms;
125
126 /* Generation count checking required? */
127 bool check_gen;
128
129 /* Modified? */
130 bool modified;
131
132 /* Transaction node in data base? */
133 bool ta_node;
134
135 /* Watch event flags. */
136 bool fire_watch;
137 bool watch_exact;
138 };
139
140 struct transaction
141 {
142 /* List of all transactions active on this connection. */
143 struct list_head list;
144
145 /* Connection this transaction is associated with. */
146 struct connection *conn;
147
148 /* Connection-local identifier for this transaction. */
149 uint32_t id;
150
151 /* Node counter. */
152 unsigned int nodes;
153
154 /* Generation when transaction started. */
155 uint64_t generation;
156
157 /* List of accessed nodes. */
158 struct list_head accessed;
159
160 /* List of changed domains - to record the changed domain entry number */
161 struct list_head changed_domains;
162
163 /* There was at least one node created in the transaction. */
164 bool node_created;
165
166 /* Flag for letting transaction fail. */
167 bool fail;
168 };
169
170 uint64_t generation;
171
172 void ta_node_created(struct transaction *trans)
173 {
174 trans->node_created = true;
175 }
176
177 static struct accessed_node *find_accessed_node(struct transaction *trans,
178 const char *name)
179 {
180 struct accessed_node *i;
181
182 list_for_each_entry(i, &trans->accessed, list)
183 if (streq(i->node, name))
184 return i;
185
186 return NULL;
187 }
188
189 static char *transaction_get_node_name(void *ctx, struct transaction *trans,
190 const char *name)
191 {
192 return talloc_asprintf(ctx, "%"PRIu64"/%s", trans->generation, name);
193 }
194
195 /*
196 * Prepend the transaction to name if node has been modified in the current
197 * transaction.
198 */
199 const char *transaction_prepend(struct connection *conn, const char *name)
200 {
201 struct accessed_node *i;
202
203 if (conn && conn->transaction) {
204 i = find_accessed_node(conn->transaction, name);
205 if (i)
206 return i->trans_name;
207 }
208
209 return name;
210 }
211
212 /*
213 * A node has been accessed.
214 *
215 * Modifying accesses (write, delete) always update the generation (global and
216 * node->generation).
217 *
218 * Accesses in a transaction will be added to the list of accessed nodes
219 * if not already done. Read type accesses will copy the node to the
220 * transaction specific data base part, write type accesses go there
221 * anyway.
222 *
223 * If not NULL, key will be supplied with name and length of name of the node
224 * to be accessed in the data base.
225 */
226 int access_node(struct connection *conn, struct node *node,
227 enum node_access_type type, const char **db_name)
228 {
229 struct accessed_node *i = NULL;
230 struct transaction *trans;
231 int ret;
232 bool introduce = false;
233
234 if (type != NODE_ACCESS_READ) {
235 node->hdr.generation = ++generation;
236 if (conn && !conn->transaction)
237 wrl_apply_debit_direct(conn);
238 }
239
240 if (!conn || !conn->transaction) {
241 /* They're changing the global database. */
242 if (db_name)
243 *db_name = node->name;
244 return 0;
245 }
246
247 trans = conn->transaction;
248
249 i = find_accessed_node(trans, node->name);
250 if (!i) {
251 if (domain_max_chk(conn, ACC_TRANSNODES, trans->nodes + 1)) {
252 ret = ENOSPC;
253 goto err;
254 }
255 i = talloc_zero(trans, struct accessed_node);
256 if (!i)
257 goto nomem;
258 i->trans_name = transaction_get_node_name(i, trans, node->name);
259 if (!i->trans_name)
260 goto nomem;
261 i->node = strchr(i->trans_name, '/') + 1;
262 if (node->hdr.generation != NO_GENERATION &&
263 node->hdr.num_perms) {
264 i->perms.p = talloc_array(i, struct xs_permissions,
265 node->hdr.num_perms);
266 if (!i->perms.p)
267 goto nomem;
268 i->perms.num = node->hdr.num_perms;
269 memcpy(i->perms.p, node->perms,
270 i->perms.num * sizeof(*i->perms.p));
271 }
272
273 introduce = true;
274 i->ta_node = false;
275 /* acc.memory < 0 means "unknown, get size from TDB". */
276 node->acc.memory = -1;
277
278 /*
279 * Additional transaction-specific node for read type. We only
280 * have to verify read nodes if we didn't write them.
281 *
282 * The node is created and written to DB here to distinguish
283 * from the write types.
284 */
285 if (type == NODE_ACCESS_READ) {
286 i->generation = node->hdr.generation;
287 i->check_gen = true;
288 if (node->hdr.generation != NO_GENERATION) {
289 ret = write_node_raw(conn, i->trans_name, node,
290 NODE_CREATE, true);
291 if (ret)
292 goto err;
293 i->ta_node = true;
294 }
295 }
296 trans->nodes++;
297 list_add_tail(&i->list, &trans->accessed);
298 }
299
300 if (type != NODE_ACCESS_READ)
301 i->modified = true;
302
303 if (introduce && type == NODE_ACCESS_DELETE)
304 /* Nothing to delete. */
305 return -1;
306
307 if (db_name) {
308 *db_name = i->trans_name;
309 if (type == NODE_ACCESS_WRITE)
310 i->ta_node = true;
311 if (type == NODE_ACCESS_DELETE)
312 i->ta_node = false;
313 }
314
315 return 0;
316
317 nomem:
318 ret = ENOMEM;
319 err:
320 talloc_free(i);
321 trans->fail = true;
322 errno = ret;
323 return ret;
324 }
325
326 /*
327 * A watch event should be fired for a node modified inside a transaction.
328 * Set the corresponding information. A non-exact event is replacing an exact
329 * one, but not the other way round.
330 */
331 void queue_watches(struct connection *conn, const char *name, bool watch_exact)
332 {
333 struct accessed_node *i;
334
335 i = find_accessed_node(conn->transaction, name);
336 if (!i) {
337 conn->transaction->fail = true;
338 return;
339 }
340
341 if (!i->fire_watch) {
342 i->fire_watch = true;
343 i->watch_exact = watch_exact;
344 } else if (!watch_exact) {
345 i->watch_exact = false;
346 }
347 }
348
349 /*
350 * Finalize transaction:
351 * Walk through accessed nodes and check generation against global data.
352 * If all entries match, read the transaction entries and write them without
353 * transaction prepended. Delete all transaction specific nodes in the data
354 * base.
355 */
356 static int finalize_transaction(struct connection *conn,
357 struct transaction *trans, bool *is_corrupt)
358 {
359 struct accessed_node *i, *n;
360 size_t size;
361 const struct node_hdr *hdr;
362 uint64_t gen;
363
364 list_for_each_entry_safe(i, n, &trans->accessed, list) {
365 if (i->check_gen) {
366 hdr = db_fetch(i->node, &size);
367 if (!hdr) {
368 gen = NO_GENERATION;
369 } else {
370 gen = hdr->generation;
371 }
372 if (i->generation != gen)
373 return EAGAIN;
374 }
375
376 /* Entries for unmodified nodes can be removed early. */
377 if (!i->modified) {
378 if (i->ta_node)
379 db_delete(conn, i->trans_name, NULL);
380 list_del(&i->list);
381 talloc_free(i);
382 }
383 }
384
385 while ((i = list_top(&trans->accessed, struct accessed_node, list))) {
386 if (i->ta_node) {
387 hdr = db_fetch(i->trans_name, &size);
388 if (hdr) {
389 /*
390 * Delete transaction entry and write it as
391 * no-TA entry. As we only hold a reference
392 * to the data, increment its ref count, then
393 * delete it from the DB. Now we own it and can
394 * drop the const attribute for changing the
395 * generation count.
396 */
397 enum write_node_mode mode;
398 struct node_hdr *own;
399
400 talloc_increase_ref_count(hdr);
401 db_delete(conn, i->trans_name, NULL);
402
403 own = (struct node_hdr *)hdr;
404 own->generation = ++generation;
405 mode = (i->generation == NO_GENERATION)
406 ? NODE_CREATE : NODE_MODIFY;
407 *is_corrupt |= db_write(conn, i->node, own,
408 size, NULL, mode, true);
409 } else {
410 *is_corrupt = true;
411 }
412 } else {
413 /*
414 * A node having been created and later deleted
415 * in this transaction will have no generation
416 * information stored.
417 */
418 if (i->generation != NO_GENERATION)
419 db_delete(conn, i->node, NULL);
420 }
421 if (i->fire_watch)
422 fire_watches(conn, trans, i->node, NULL, i->watch_exact,
423 i->perms.p ? &i->perms : NULL);
424
425 list_del(&i->list);
426 talloc_free(i);
427 }
428
429 return 0;
430 }
431
432 static int destroy_transaction(void *_transaction)
433 {
434 struct transaction *trans = _transaction;
435 struct accessed_node *i;
436
437 wrl_ntransactions--;
438 trace_destroy(trans, "transaction");
439 while ((i = list_top(&trans->accessed, struct accessed_node, list))) {
440 if (i->ta_node)
441 db_delete(trans->conn, i->trans_name, NULL);
442 list_del(&i->list);
443 talloc_free(i);
444 }
445
446 return 0;
447 }
448
449 struct transaction *transaction_lookup(struct connection *conn, uint32_t id)
450 {
451 struct transaction *trans;
452
453 if (id == 0)
454 return NULL;
455
456 list_for_each_entry(trans, &conn->transaction_list, list)
457 if (trans->id == id)
458 return trans;
459
460 return ERR_PTR(-ENOENT);
461 }
462
463 int do_transaction_start(const void *ctx, struct connection *conn,
464 struct buffered_data *in)
465 {
466 struct transaction *trans, *exists;
467 char id_str[20];
468
469 /* We don't support nested transactions. */
470 if (conn->transaction)
471 return EBUSY;
472
473 if (domain_transaction_get(conn) > hard_quotas[ACC_TRANS].val)
474 return ENOSPC;
475
476 /* Attach transaction to ctx for autofree until it's complete */
477 trans = talloc_zero(ctx, struct transaction);
478 if (!trans)
479 return ENOMEM;
480
481 trace_create(trans, "transaction");
482 INIT_LIST_HEAD(&trans->accessed);
483 INIT_LIST_HEAD(&trans->changed_domains);
484 trans->conn = conn;
485 trans->fail = false;
486 trans->generation = ++generation;
487
488 /* Pick an unused transaction identifier. */
489 do {
490 trans->id = conn->next_transaction_id;
491 exists = transaction_lookup(conn, conn->next_transaction_id++);
492 } while (!IS_ERR(exists));
493
494 if (list_empty(&conn->transaction_list))
495 conn->ta_start_time = time(NULL);
496
497 /* Now we own it. */
498 list_add_tail(&trans->list, &conn->transaction_list);
499 talloc_steal(conn, trans);
500 talloc_set_destructor(trans, destroy_transaction);
501 domain_transaction_inc(conn);
502 wrl_ntransactions++;
503
504 snprintf(id_str, sizeof(id_str), "%u", trans->id);
505 send_reply(conn, XS_TRANSACTION_START, id_str, strlen(id_str)+1);
506
507 return 0;
508 }
509
510 int do_transaction_end(const void *ctx, struct connection *conn,
511 struct buffered_data *in)
512 {
513 const char *arg = onearg(in);
514 struct transaction *trans;
515 bool is_corrupt = false;
516 bool chk_quota;
517 int ret;
518
519 if (!arg || (!streq(arg, "T") && !streq(arg, "F")))
520 return EINVAL;
521
522 if ((trans = conn->transaction) == NULL)
523 return ENOENT;
524
525 conn->transaction = NULL;
526 list_del(&trans->list);
527 domain_transaction_dec(conn);
528 if (list_empty(&conn->transaction_list))
529 conn->ta_start_time = 0;
530
531 chk_quota = trans->node_created && domain_is_unprivileged(conn);
532
533 /* Attach transaction to ctx for auto-cleanup */
534 talloc_steal(ctx, trans);
535
536 if (streq(arg, "T")) {
537 if (trans->fail)
538 return ENOMEM;
539 ret = acc_fix_domains(&trans->changed_domains, chk_quota,
540 false);
541 if (ret)
542 return ret;
543 ret = finalize_transaction(conn, trans, &is_corrupt);
544 if (ret)
545 return ret;
546
547 wrl_apply_debit_trans_commit(conn);
548
549 /* fix domain entry for each changed domain */
550 acc_fix_domains(&trans->changed_domains, false, true);
551
552 if (is_corrupt)
553 corrupt(conn, "transaction inconsistency");
554 }
555 send_ack(conn, XS_TRANSACTION_END);
556
557 return 0;
558 }
559
560 struct list_head *transaction_get_changed_domains(struct transaction *trans)
561 {
562 return &trans->changed_domains;
563 }
564
565 void fail_transaction(struct transaction *trans)
566 {
567 trans->fail = true;
568 }
569
570 void conn_delete_all_transactions(struct connection *conn)
571 {
572 struct transaction *trans;
573
574 while ((trans = list_top(&conn->transaction_list,
575 struct transaction, list))) {
576 list_del(&trans->list);
577 talloc_free(trans);
578 }
579
580 assert(conn->transaction == NULL);
581
582 conn->ta_start_time = 0;
583 }
584
585 int check_transactions(struct hashtable *hash)
586 {
587 struct connection *conn;
588 struct transaction *trans;
589 struct accessed_node *i;
590 char *tname;
591
592 list_for_each_entry(conn, &connections, list) {
593 list_for_each_entry(trans, &conn->transaction_list, list) {
594 tname = talloc_asprintf(trans, "%"PRIu64,
595 trans->generation);
596 if (!tname || remember_string(hash, tname))
597 goto nomem;
598
599 list_for_each_entry(i, &trans->accessed, list) {
600 if (!i->ta_node)
601 continue;
602 if (remember_string(hash, i->trans_name))
603 goto nomem;
604 }
605
606 talloc_free(tname);
607 }
608 }
609
610 return 0;
611
612 nomem:
613 talloc_free(tname);
614 return ENOMEM;
615 }
616
617 /*
618 * Local variables:
619 * mode: C
620 * c-file-style: "linux"
621 * indent-tabs-mode: t
622 * c-basic-offset: 8
623 * tab-width: 8
624 * End:
625 */