Bug Summary

File:build-analysis/../src/lib/s4/src/lib/relation.c
Warning:line 241, column 2
Potential leak of memory pointed to by 'entry'

Annotated Source Code

1/* S4 - An XMMS2 medialib backend
2 * Copyright (C) 2009, 2010 Sivert Berg
3 *
4 * This library is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU Lesser General Public
6 * License as published by the Free Software Foundation; either
7 * version 2.1 of the License, or (at your option) any later version.
8 *
9 * This library is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 * Lesser General Public License for more details.
13 */
14
15#include "s4_priv.h"
16#include <stdlib.h>
17#include <string.h>
18
19typedef struct {
20 const char *key;
21 const s4_val_t *val;
22 const char *src;
23} entry_data_t;
24
25typedef struct {
26 s4_lock_t *lock;
27 const char *key;
28 const s4_val_t *val;
29 int size, alloc;
30
31 entry_data_t *data;
32} entry_t;
33
34struct s4_entry_data_St {
35 entry_t *entry;
36 const char *prev_key;
37 const s4_val_t *prev_val;
38};
39
40#define LINEAR_SEARCH_SIZE0 0
41
42/**
43 * @defgroup Entry Entry
44 * @ingroup S4
45 * @brief The in-memory database.
46 *
47 * @{
48 */
49
50/**
51 * @{
52 * @internal
53 */
54
55s4_entry_data_t *_entry_create_data ()
56{
57 s4_entry_data_t *ret = calloc (1, sizeof (s4_entry_data_t));
58
59 return ret;
60}
61
62void _entry_free_data (s4_entry_data_t *data)
63{
64 free (data);
65}
66
67/**
68 * Searches an entry for key
69 *
70 * @param entry The entry to search
71 * @param key The key to search for
72 * @return The index of the item before the first item with key=key,
73 * or the index of the first item with key=key.
74 */
75static int _entry_search (entry_t *entry, const char *key)
76{
77 int lo = 0;
78 int hi = entry->size;
79
80 while ((hi - lo) > LINEAR_SEARCH_SIZE0) {
81 int m = (hi + lo) / 2;
82
83 if (entry->data[m].key < key)
84 lo = m + 1;
85 else
86 hi = m;
87 }
88
89 for (; lo < hi && entry->data[lo].key < key; lo++);
90
91 return lo;
92}
93
94/**
95 * Inserts a key,value,source tuple into an entry
96 *
97 * @param entry The entry to insert into
98 * @param key The key to insert
99 * @param val The value to insert
100 * @param src The source to insert
101 * @return 0 if the tuple already exists, non-zero otherwise
102 */
103static int _entry_insert (entry_t *entry, const char *key, const s4_val_t *val, const char *src)
104{
105 int i = _entry_search (entry, key);
106
107 for (; i < entry->size && entry->data[i].key == key; i++) {
108 if (entry->data[i].src == src && !s4_val_cmp (entry->data[i].val, val, S4_CMP_BINARY))
109 return 0;
110 }
111
112 if (entry->size >= entry->alloc) {
113 entry->alloc *= 2;
114 entry->data = realloc (entry->data, sizeof (entry_data_t) * entry->alloc);
115 }
116
117 memmove (entry->data + i + 1, entry->data + i, (entry->size - i) * sizeof (entry_data_t));
118 entry->size++;
119
120 entry->data[i].key = key;
121 entry->data[i].val = val;
122 entry->data[i].src = src;
123
124 return 1;
125}
126
127/**
128 * Deletes a key,value,source tuple from an entry
129 *
130 * @param entry The entry to delete from
131 * @param key The key to delete
132 * @param val The value to delete
133 * @param src The source to delete
134 * @return 0 if the tuple was not found, 1 otherwise
135 */
136static int _entry_delete (entry_t *entry, const char *key, const s4_val_t *val, const char *src)
137{
138 int i = _entry_search (entry, key);
139 int found = 0;
140
141 for (; i < entry->size && entry->data[i].key == key; i++) {
142 if (entry->data[i].src == src && !s4_val_cmp (entry->data[i].val, val, S4_CMP_BINARY)) {
143 found = 1;
144 break;
145 }
146 }
147
148 if (!found)
149 return 0;
150
151 memmove (entry->data + i, entry->data + i + 1, (entry->size - i - 1) * sizeof (entry_data_t));
152 entry->size--;
153
154 return 1;
155}
156
157/**
158 * Creates a new entry
159 *
160 * @param key The key of the entry
161 * @param val The value of the entry
162 * @return A new empty entry
163 */
164static entry_t *_entry_create (const char *key, const s4_val_t *val)
165{
166 entry_t *entry = malloc (sizeof (entry_t));
6
←
Memory is allocated
→
167
168 entry->lock = _lock_alloc ();
169 entry->key = key;
170 entry->val = val;
171 entry->size = 0;
172 entry->alloc = 1;
173
174 entry->data = malloc (sizeof (entry_data_t) * entry->alloc);
175
176 return entry;
177}
178
179static int _entry_lock_shared (entry_t *entry, s4_transaction_t *trans)
180{
181 return _lock_shared (entry->lock, trans);
182}
183
184static int _entry_lock_exclusive (entry_t *entry, s4_transaction_t *trans)
185{
186 return _lock_exclusive (entry->lock, trans);
187}
188
189/**
190 * @}
191 */
192
193/**
194 * Adds a new relation to a database
195 *
196 * @param s4 The database to add to
197 * @param key_a The key of the first entry
198 * @param val_a The value of the first entry
199 * @param key_b The key of the second entry
200 * @param val_b The value of the second entry
201 * @param src The source that made the relation
202 * @return non-zero if everything went alrite, 0 otherwise
203 */
204int _s4_add (s4_transaction_t *trans, const char *key_a, const s4_val_t *val_a,
205 const char *key_b, const s4_val_t *val_b, const char *src)
206{
207 s4_index_t *index;
208 entry_t *entry;
209 GList *entries;
210 int ret;
211 s4_t *s4 = _transaction_get_db (trans);
212
213 index = _index_get_a (s4, key_a, 1);
214 if (!_index_lock_shared (index, trans)) goto deadlocked;
1
Assuming the condition is false
→
2
←
Taking false branch
→
215 entries = _index_search (index, NULL((void*)0), (void*)val_a);
216
217 if (entries == NULL((void*)0)) {
3
←
Assuming 'entries' is equal to NULL
→
4
←
Taking true branch
→
218 entry = _entry_create (key_a, val_a);
5
←
Calling '_entry_create'
→
7
←
Returned allocated memory
→
219 if (!_index_lock_exclusive (index, trans)) goto deadlocked;
8
←
Assuming the condition is true
→
9
←
Taking true branch
→
10
←
Control jumps to line 241
→
220 _index_insert (index, val_a, entry);
221 } else {
222 entry = entries->data;
223 g_list_free (entries);
224 }
225
226 if (!_entry_lock_exclusive (entry, trans)) goto deadlocked;
227 ret = _entry_insert (entry, key_b, val_b, src);
228
229 if (ret) {
230 index = _index_get_b (s4, key_b);
231
232 if (index != NULL((void*)0)) {
233 if (!_index_lock_exclusive (index, trans)) goto deadlocked;
234 _index_insert (index, val_b, entry);
235 }
236 }
237
238 return ret;
239
240deadlocked:
241 _transaction_set_deadlocked (trans);
11
←
Potential leak of memory pointed to by 'entry'
242 return 0;
243}
244
245/* An internal function of the above functions. It expects all keys
246 * and values passed to be internal, so no copying have to be done.
247 * It also exploits that pairs with the same key_a and value_a are
248 * written next to each other on file, and it can therefore save
249 * many index searches.
250 */
251int _s4_add_internal (s4_t *s4, const char *key_a, const s4_val_t *value_a,
252 const char *key_b, const s4_val_t *value_b, const char *src)
253{
254 int ret;
255 s4_index_t *index;
256
257 /* If key_a and value_a are equal to the key and value of entry
258 * it don't have to search the index to find entry
259 */
260 if (s4->entry_data->prev_key != key_a
261 || s4->entry_data->prev_val != value_a) {
262 GList *entries;
263
264 index = _index_get_a (s4, key_a, 1);
265 entries = _index_search (index, NULL((void*)0), (void*)value_a);
266
267 if (entries == NULL((void*)0)) {
268 s4->entry_data->entry = _entry_create (key_a, value_a);
269 _index_insert (index, value_a, s4->entry_data->entry);
270 } else {
271 s4->entry_data->entry = entries->data;
272 g_list_free (entries);
273 }
274
275 s4->entry_data->prev_key = key_a;
276 s4->entry_data->prev_val = value_a;
277 }
278
279 ret = _entry_insert (s4->entry_data->entry, key_b, value_b, src);
280
281 if (ret) {
282 index = _index_get_b (s4, key_b);
283
284 if (index != NULL((void*)0)) {
285 _index_insert (index, value_b, s4->entry_data->entry);
286 }
287 }
288
289 return ret;
290}
291
292/**
293 * Deletes a relation from a database
294 *
295 * @param s4 The database to delete from
296 * @param key_a The key of the first entry
297 * @param val_a The value of the first entry
298 * @param key_b The key of the second entry
299 * @param val_b The value of the second entry
300 * @param src The source that made the relation
301 * @return non-zero if everything went alrite, 0 otherwise
302 */
303int _s4_del (s4_transaction_t *trans, const char *key_a, const s4_val_t *val_a,
304 const char *key_b, const s4_val_t *val_b, const char *src)
305{
306 s4_index_t *index;
307 entry_t *entry;
308 GList *entries;
309 int ret;
310 s4_t *s4 = _transaction_get_db (trans);
311
312 index = _index_get_a (s4, key_a, 0);
313 if (index == NULL((void*)0)) {
314 return 0;
315 }
316
317 if (!_index_lock_shared (index, trans)) goto deadlocked;
318 entries = _index_search (index, NULL((void*)0), (void*)val_a);
319
320 if (entries == NULL((void*)0)) {
321 return 0;
322 } else {
323 entry = entries->data;
324 g_list_free (entries);
325 }
326
327 if (!_entry_lock_exclusive (entry, trans)) goto deadlocked;
328 ret = _entry_delete (entry, key_b, val_b, src);
329
330 if (ret) {
331 index = _index_get_b (s4, key_b);
332
333 if (index != NULL((void*)0)) {
334 if (!_index_lock_exclusive (index, trans)) goto deadlocked;
335 _index_delete (index, val_b, entry);
336 }
337 }
338
339 return ret;
340
341deadlocked:
342 _transaction_set_deadlocked (trans);
343 return 0;
344}
345
346/**
347 * @{
348 * @internal
349 */
350
351/**
352 * An index function that matches everything
353 *
354 * @return 0
355 */
356static int _everything (void)
357{
358 return 0;
359}
360
361/**
362 * Frees all relations in a database
363 *
364 * @param s4 The database to free in
365 */
366void _free_relations (s4_t *s4)
367{
368 s4_index_t *index;
369 GList *indexes, *entries;
370
371 indexes = _index_get_all_a (s4);
372
373 for (; indexes != NULL((void*)0); indexes = g_list_delete_link (indexes, indexes)) {
374 index = indexes->data;
375 entries = _index_search (index, (index_function_t)_everything, NULL((void*)0));
376
377 for (; entries != NULL((void*)0); entries = g_list_delete_link (entries, entries)) {
378 entry_t *entry = entries->data;
379
380 _lock_free (entry->lock);
381 free (entry->data);
382 free (entry);
383 }
384 }
385}
386
387typedef struct {
388 s4_t *s4;
389 entry_t *l;
390} check_data_t;
391
392/**
393 * Checks an entry against a condition
394 *
395 * @param cond The condition to check
396 * @param d The database and entry to check
397 * @return 0 if the entry matched, non-zero otherwise
398 */
399static int _check_cond (s4_condition_t *cond, void *d)
400{
401 check_data_t *data = d;
402 entry_t *l = data->l;
403 int ret = 1;
404 int i;
405
406 if (s4_cond_is_combiner (cond)) {
407 ret = s4_cond_get_combine_function (cond)(cond, _check_cond, d);
408 } else if (s4_cond_is_filter (cond)) {
409 const char *key = s4_cond_get_key (cond);
410 int null = key == NULL((void*)0);
411
412 if ((s4_cond_get_flags (cond) & S4_COND_PARENT1)) {
413 if (key == l->key || null) {
414 ret = s4_cond_get_filter_function (cond)(l->val, cond);
415 }
416 } else {
417 i = 0;
418 do {
419 s4_sourcepref_t *sp = s4_cond_get_sourcepref (cond);
420 int start, src, best_src = INT_MAX2147483647;
421
422 if (null) {
423 key = l->data[i].key;
424 }
425
426 start = _entry_search (l, key);
427
428 for (i = start; i < l->size && l->data[i].key == key; i++) {
429 if ((src = s4_sourcepref_get_priority (sp, l->data[i].src)) < best_src) {
430 best_src = src;
431 }
432 }
433 for (i = start; i < l->size && ret && l->data[i].key == key; i++) {
434 if (best_src < INT_MAX2147483647 &&
435 s4_sourcepref_get_priority (sp, l->data[i].src) == best_src) {
436 ret = s4_cond_get_filter_function (cond)(l->data[i].val, cond);
437 }
438 }
439 } while (i < l->size && ret && null);
440 }
441 }
442
443 return ret;
444}
445
446/**
447 * Fetches values from an entry
448 *
449 * @param s4 The database the entry lives in
450 * @param l The entry to fetch from
451 * @param fs The fetchspec that tells us what to fetch
452 * @return An array of results
453 */
454static s4_resultrow_t *_fetch (s4_t *s4, entry_t *l, s4_fetchspec_t *fs)
455{
456 s4_resultrow_t *row;
457 int k,f;
458 int fetch_size = s4_fetchspec_size (fs);
459
460 row = s4_resultrow_create (fetch_size);
461
462 for (k = 0; k < fetch_size; k++) {
463 const char *fkey = s4_fetchspec_get_key (fs, k);
464 int flags = s4_fetchspec_get_flags (fs, k);
465 int null = fkey == NULL((void*)0);
466 s4_result_t *result;
467 s4_sourcepref_t *sp = s4_fetchspec_get_sourcepref (fs, k);
468
469 result = NULL((void*)0);
470 f = 0;
471
472 if ((flags & S4_FETCH_PARENT1) && (fkey == l->key || null)) {
473 result = s4_result_create (result, l->key, l->val, NULL((void*)0));
474 }
475
476 if (flags & S4_FETCH_DATA2) {
477 do {
478 int src, start, best_src = INT_MAX2147483647;
479
480 if (null && l->size > 0) {
481 fkey = l->data[f].key;
482 }
483
484 start = _entry_search (l, fkey);
485
486 for (f = start; f < l->size && l->data[f].key == fkey; f++) {
487 if ((src = s4_sourcepref_get_priority (sp, l->data[f].src)) < best_src) {
488 best_src = src;
489 }
490 }
491 for (f = start; f < l->size && l->data[f].key == fkey; f++) {
492 if (best_src < INT_MAX2147483647 &&
493 s4_sourcepref_get_priority (sp, l->data[f].src) == best_src) {
494 result = s4_result_create (result, l->data[f].key,
495 l->data[f].val, l->data[f].src);
496 }
497 }
498 } while (f < l->size && null);
499 }
500
501 s4_resultrow_set_col (row, k, result);
502 }
503
504 return row;
505}
506
507/**
508 * @}
509 */
510
511/**
512 * Queries a database for all entries matching a condition,
513 * then fetches data from them.
514 *
515 * @param trans The transaction this query belongs to.
516 * @param fs The fetchspec to use when fetching data
517 * @param cond The condition to check entries against
518 * @return A resultset with a row for every entry that matched
519 */
520s4_resultset_t *_s4_query (
521 s4_transaction_t *trans,
522 s4_fetchspec_t *fs,
523 s4_condition_t *cond)
524{
525 check_data_t data;
526 GList *entries;
527 s4_index_t *index;
528 s4_resultset_t *ret = s4_resultset_create (s4_fetchspec_size (fs));
529 s4_t *s4 = _transaction_get_db (trans);
530
531 s4_cond_update_key (cond, s4);
532 s4_fetchspec_update_key (s4, fs);
533
534 if (s4_cond_is_filter (cond)
535 && (s4_cond_get_flags (cond) & S4_COND_PARENT1)
536 && s4_cond_get_key (cond) != NULL((void*)0)) {
537 index = _index_get_a (s4, s4_cond_get_key (cond), 0);
538
539 if (index == NULL((void*)0)) {
540 entries = NULL((void*)0);
541 } else {
542 if (!_index_lock_shared (index, trans)) goto deadlocked;
543 if (s4_cond_is_monotonic (cond)) {
544 entries = _index_search (index, (index_function_t)s4_cond_get_filter_function (cond), cond);
545 } else {
546 entries = _index_lsearch (index, (index_function_t)s4_cond_get_filter_function (cond), cond);
547 }
548 }
549 } else if (s4_cond_is_filter (cond)
550 && s4_cond_get_key (cond) != NULL((void*)0)
551 && (index = _index_get_b (s4, s4_cond_get_key (cond))) != NULL((void*)0)) {
552 if (!_index_lock_shared (index, trans)) goto deadlocked;
553 if (s4_cond_is_monotonic (cond)) {
554 entries = _index_search (index, (index_function_t)s4_cond_get_filter_function (cond), cond);
555 } else {
556 entries = _index_lsearch (index, (index_function_t)s4_cond_get_filter_function (cond), cond);
557 }
558 } else {
559 GList *indices;
560 indices = _index_get_all_a (s4);
561
562 for (entries = NULL((void*)0); indices != NULL((void*)0); indices = g_list_delete_link (indices, indices)) {
563 if (!_index_lock_shared (indices->data, trans)) goto deadlocked;
564 entries = g_list_concat (entries, _index_lsearch (indices->data, (index_function_t)_everything, NULL((void*)0)));
565 }
566 }
567
568 data.s4 = s4;
569 for (; entries != NULL((void*)0); entries = g_list_delete_link (entries, entries)) {
570 entry_t *entry = entries->data;
571 data.l = entry;
572
573 if (!_entry_lock_shared (entry, trans)) goto deadlocked;
574 if (entry->size != 0 && !_check_cond (cond, &data))
575 s4_resultset_add_row (ret, _fetch (s4, entry, fs));
576 }
577
578 return ret;
579
580deadlocked:
581 _transaction_set_deadlocked (trans);
582 return ret;
583}
584
585/**
586 * @}
587 */