Branch data Line data Source code
1 : : /*
2 : : * libdpkg - Debian packaging suite library routines
3 : : * pkg-hash.c - low level package database routines (hash tables, etc.)
4 : : *
5 : : * Copyright © 1995 Ian Jackson <ijackson@chiark.greenend.org.uk>
6 : : * Copyright © 2008-2014 Guillem Jover <guillem@debian.org>
7 : : * Copyright © 2011 Linaro Limited
8 : : * Copyright © 2011 Raphaël Hertzog <hertzog@debian.org>
9 : : *
10 : : * This is free software; you can redistribute it and/or modify
11 : : * it under the terms of the GNU General Public License as published by
12 : : * the Free Software Foundation; either version 2 of the License, or
13 : : * (at your option) any later version.
14 : : *
15 : : * This is distributed in the hope that it will be useful,
16 : : * but WITHOUT ANY WARRANTY; without even the implied warranty of
17 : : * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18 : : * GNU General Public License for more details.
19 : : *
20 : : * You should have received a copy of the GNU General Public License
21 : : * along with this program. If not, see <https://www.gnu.org/licenses/>.
22 : : */
23 : :
24 : : #include <config.h>
25 : : #include <compat.h>
26 : :
27 : : #include <string.h>
28 : : #include <stdlib.h>
29 : :
30 : : #include <dpkg/i18n.h>
31 : : #include <dpkg/c-ctype.h>
32 : : #include <dpkg/dpkg.h>
33 : : #include <dpkg/dpkg-db.h>
34 : : #include <dpkg/string.h>
35 : : #include <dpkg/arch.h>
36 : :
37 : : /*
38 : : * This must always be a prime for optimal performance.
39 : : *
40 : : * We use a number that is close to the amount of packages currently present
41 : : * in a Debian suite, so that installed and available packages do not add
42 : : * tons of collisions.
43 : : *
44 : : * The memory usage is «BINS * sizeof(void *)».
45 : : */
46 : : #define BINS 65521
47 : :
48 : : static struct pkgset *bins[BINS];
49 : : static int npkg, nset;
50 : :
51 : : /**
52 : : * Return the package set with the given name.
53 : : *
54 : : * If the package already exists in the internal database, then it returns
55 : : * the existing structure. Otherwise it allocates a new one and will return
56 : : * it. The actual name associated to the package set is a lowercase version
57 : : * of the name given in parameter.
58 : : *
59 : : * A package set (struct pkgset) can be composed of multiple package instances
60 : : * (struct pkginfo) where each instance is distinguished by its architecture
61 : : * (as recorded in pkg.installed.arch and pkg.available.arch).
62 : : *
63 : : * @param inname Name of the package set.
64 : : *
65 : : * @return The package set.
66 : : */
67 : : struct pkgset *
68 : 113 : pkg_hash_find_set(const char *inname)
69 : : {
70 : : struct pkgset **setp, *new_set;
71 : 113 : char *name = m_strdup(inname), *p;
72 : :
73 : 113 : p= name;
74 [ + + ]: 1464 : while (*p) {
75 : 1351 : *p = c_tolower(*p);
76 : 1351 : p++;
77 : : }
78 : :
79 : 113 : setp = bins + (str_fnv_hash(name) % (BINS));
80 [ + + - + ]: 113 : while (*setp && strcasecmp((*setp)->name, name))
81 : 0 : setp = &(*setp)->next;
82 [ + + ]: 113 : if (*setp) {
83 : 46 : free(name);
84 : 46 : return *setp;
85 : : }
86 : :
87 : 67 : new_set = nfmalloc(sizeof(*new_set));
88 : 67 : pkgset_blank(new_set);
89 : 67 : new_set->name = nfstrsave(name);
90 : 67 : new_set->next = NULL;
91 : 67 : *setp = new_set;
92 : 67 : nset++;
93 : 67 : npkg++;
94 : :
95 : 67 : free(name);
96 : :
97 : 67 : return new_set;
98 : : }
99 : :
100 : : /**
101 : : * Return the singleton package instance from a package set.
102 : : *
103 : : * This means, if none are installed either an instance with native or
104 : : * all arch or the first if none found, the single installed instance,
105 : : * or NULL if more than one instance is installed.
106 : : *
107 : : * @param set The package set to use.
108 : : *
109 : : * @return The singleton package instance.
110 : : */
111 : : struct pkginfo *
112 : 3 : pkg_hash_get_singleton(struct pkgset *set)
113 : : {
114 : : struct pkginfo *pkg;
115 : :
116 [ + + + ]: 3 : switch (pkgset_installed_instances(set)) {
117 : 1 : case 0:
118 : : /* Pick an available candidate. */
119 [ + + ]: 2 : for (pkg = &set->pkg; pkg; pkg = pkg->arch_next) {
120 : 1 : const struct dpkg_arch *arch = pkg->available.arch;
121 : :
122 [ + - - + ]: 1 : if (arch->type == DPKG_ARCH_NATIVE || arch->type == DPKG_ARCH_ALL)
123 : 0 : return pkg;
124 : : }
125 : : /* Or failing that, the first entry. */
126 : 1 : return &set->pkg;
127 : 1 : case 1:
128 [ + - ]: 1 : for (pkg = &set->pkg; pkg; pkg = pkg->arch_next) {
129 [ + - ]: 1 : if (pkg->status > PKG_STAT_NOTINSTALLED)
130 : 1 : return pkg;
131 : : }
132 : 0 : internerr("pkgset '%s' should have one installed instance", set->name);
133 : 1 : default:
134 : 1 : return NULL;
135 : : }
136 : : }
137 : :
138 : : /**
139 : : * Return the singleton package instance with the given name.
140 : : *
141 : : * @param name The package name.
142 : : *
143 : : * @return The package instance.
144 : : */
145 : : struct pkginfo *
146 : 2 : pkg_hash_find_singleton(const char *name)
147 : : {
148 : : struct pkgset *set;
149 : : struct pkginfo *pkg;
150 : :
151 : 2 : set = pkg_hash_find_set(name);
152 : 2 : pkg = pkg_hash_get_singleton(set);
153 [ - + ]: 2 : if (pkg == NULL)
154 : 0 : ohshit(_("ambiguous package name '%s' with more "
155 : : "than one installed instance"), set->name);
156 : :
157 : 2 : return pkg;
158 : : }
159 : :
160 : : /**
161 : : * Return the package instance in a set with the given architecture.
162 : : *
163 : : * It traverse the various instances to find out whether there's one
164 : : * matching the given architecture. If found, it returns it. Otherwise it
165 : : * allocates a new instance and registers it in the package set before
166 : : * returning it.
167 : : *
168 : : * @param set The package set to use.
169 : : * @param arch The requested architecture.
170 : : *
171 : : * @return The package instance.
172 : : */
173 : : struct pkginfo *
174 : 29 : pkg_hash_get_pkg(struct pkgset *set, const struct dpkg_arch *arch)
175 : : {
176 : : struct pkginfo *pkg, **pkgp;
177 : :
178 [ - + ]: 29 : if (arch == NULL)
179 : 0 : internerr("arch argument is NULL");
180 [ - + ]: 29 : if (arch->type == DPKG_ARCH_NONE)
181 : 0 : internerr("arch argument is none");
182 : :
183 : 29 : pkg = &set->pkg;
184 : :
185 : : /* If there's a single unused slot, let's use that. */
186 [ + + + - ]: 29 : if (pkg->installed.arch->type == DPKG_ARCH_NONE && pkg->arch_next == NULL) {
187 : : /* We can only initialize the arch pkgbin members, because those are used
188 : : * to find instances, anything else will be overwritten at parse time. */
189 : 26 : pkg->installed.arch = arch;
190 : 26 : pkg->available.arch = arch;
191 : 26 : return pkg;
192 : : }
193 : :
194 : : /* Match the slot with the most appropriate architecture. The installed
195 : : * architecture always has preference over the available one, as there's
196 : : * a small time window on cross-grades, where they might differ. */
197 [ + + ]: 6 : for (pkgp = &pkg; *pkgp; pkgp = &(*pkgp)->arch_next) {
198 [ + + ]: 4 : if ((*pkgp)->installed.arch == arch)
199 : 1 : return *pkgp;
200 : : }
201 : :
202 : : /* Need to create a new instance for the wanted architecture. */
203 : 2 : pkg = nfmalloc(sizeof(*pkg));
204 : 2 : pkg_blank(pkg);
205 : 2 : pkg->set = set;
206 : 2 : pkg->arch_next = NULL;
207 : : /* We can only initialize the arch pkgbin members, because those are used
208 : : * to find instances, anything else will be overwritten at parse time. */
209 : 2 : pkg->installed.arch = arch;
210 : 2 : pkg->available.arch = arch;
211 : 2 : *pkgp = pkg;
212 : 2 : npkg++;
213 : :
214 : 2 : return pkg;
215 : : }
216 : :
217 : : /**
218 : : * Return the package instance with the given name and architecture.
219 : : *
220 : : * @param name The package name.
221 : : * @param arch The requested architecture.
222 : : *
223 : : * @return The package instance.
224 : : */
225 : : struct pkginfo *
226 : 5 : pkg_hash_find_pkg(const char *name, const struct dpkg_arch *arch)
227 : : {
228 : : struct pkgset *set;
229 : : struct pkginfo *pkg;
230 : :
231 : 5 : set = pkg_hash_find_set(name);
232 : 5 : pkg = pkg_hash_get_pkg(set, arch);
233 : :
234 : 5 : return pkg;
235 : : }
236 : :
237 : : /**
238 : : * Return the number of package sets available in the database.
239 : : *
240 : : * @return The number of package sets.
241 : : */
242 : : int
243 : 14 : pkg_hash_count_set(void)
244 : : {
245 : 14 : return nset;
246 : : }
247 : :
248 : : /**
249 : : * Return the number of package instances available in the database.
250 : : *
251 : : * @return The number of package instances.
252 : : */
253 : : int
254 : 14 : pkg_hash_count_pkg(void)
255 : : {
256 : 14 : return npkg;
257 : : }
258 : :
259 : : struct pkg_hash_iter {
260 : : struct pkginfo *pkg;
261 : : int nbinn;
262 : : };
263 : :
264 : : /**
265 : : * Create a new package iterator.
266 : : *
267 : : * It can iterate either over package sets or over package instances.
268 : : *
269 : : * @return The iterator.
270 : : */
271 : : struct pkg_hash_iter *
272 : 8 : pkg_hash_iter_new(void)
273 : : {
274 : : struct pkg_hash_iter *iter;
275 : :
276 : 8 : iter = m_malloc(sizeof(*iter));
277 : 8 : iter->pkg = NULL;
278 : 8 : iter->nbinn = 0;
279 : :
280 : 8 : return iter;
281 : : }
282 : :
283 : : /**
284 : : * Return the next package set in the database.
285 : : *
286 : : * If no further package set is available, it will return NULL.
287 : : *
288 : : * @name iter The iterator.
289 : : *
290 : : * @return A package set.
291 : : */
292 : : struct pkgset *
293 : 4 : pkg_hash_iter_next_set(struct pkg_hash_iter *iter)
294 : : {
295 : : struct pkgset *set;
296 : :
297 [ + + ]: 65525 : while (!iter->pkg) {
298 [ + + ]: 65522 : if (iter->nbinn >= BINS)
299 : 1 : return NULL;
300 [ + + ]: 65521 : if (bins[iter->nbinn])
301 : 3 : iter->pkg = &bins[iter->nbinn]->pkg;
302 : 65521 : iter->nbinn++;
303 : : }
304 : :
305 : 3 : set = iter->pkg->set;
306 [ - + ]: 3 : if (set->next)
307 : 0 : iter->pkg = &set->next->pkg;
308 : : else
309 : 3 : iter->pkg = NULL;
310 : :
311 : 3 : return set;
312 : : }
313 : :
314 : : /**
315 : : * Return the next package instance in the database.
316 : : *
317 : : * If no further package instance is available, it will return NULL. Note
318 : : * that it will return all instances of a given package set in sequential
319 : : * order. The first instance for a given package set will always correspond
320 : : * to the native architecture even if that package is not installed or
321 : : * available.
322 : : *
323 : : * @name iter The iterator.
324 : : *
325 : : * @return A package instance.
326 : : */
327 : : struct pkginfo *
328 : 12 : pkg_hash_iter_next_pkg(struct pkg_hash_iter *iter)
329 : : {
330 : : struct pkginfo *pkg;
331 : :
332 [ + + ]: 458659 : while (!iter->pkg) {
333 [ + + ]: 458654 : if (iter->nbinn >= BINS)
334 : 7 : return NULL;
335 [ + + ]: 458647 : if (bins[iter->nbinn])
336 : 3 : iter->pkg = &bins[iter->nbinn]->pkg;
337 : 458647 : iter->nbinn++;
338 : : }
339 : :
340 : 5 : pkg = iter->pkg;
341 [ + + ]: 5 : if (pkg->arch_next)
342 : 2 : iter->pkg = pkg->arch_next;
343 [ - + ]: 3 : else if (pkg->set->next)
344 : 0 : iter->pkg = &pkg->set->next->pkg;
345 : : else
346 : 3 : iter->pkg = NULL;
347 : :
348 : 5 : return pkg;
349 : : }
350 : :
351 : : /**
352 : : * Free the package database iterator.
353 : : *
354 : : * @name iter The iterator.
355 : : */
356 : : void
357 : 8 : pkg_hash_iter_free(struct pkg_hash_iter *iter)
358 : : {
359 : 8 : free(iter);
360 : 8 : }
361 : :
362 : : void
363 : 53 : pkg_hash_reset(void)
364 : : {
365 : 53 : dpkg_arch_reset_list();
366 : 53 : nffreeall();
367 : 53 : nset = 0;
368 : 53 : npkg = 0;
369 : 53 : memset(bins, 0, sizeof(bins));
370 : 53 : }
371 : :
372 : : void
373 : 0 : pkg_hash_report(FILE *file)
374 : : {
375 : : int i, c;
376 : : struct pkgset *pkg;
377 : : int *freq;
378 : 0 : int empty = 0, used = 0, collided = 0;
379 : :
380 : 0 : freq = m_malloc(sizeof(int) * nset + 1);
381 [ # # ]: 0 : for (i = 0; i <= nset; i++)
382 : 0 : freq[i] = 0;
383 [ # # ]: 0 : for (i=0; i<BINS; i++) {
384 [ # # ]: 0 : for (c=0, pkg= bins[i]; pkg; c++, pkg= pkg->next);
385 : 0 : fprintf(file, "pkg-hash: bin %5d has %7d\n", i, c);
386 [ # # ]: 0 : if (c == 0)
387 : 0 : empty++;
388 [ # # ]: 0 : else if (c == 1)
389 : 0 : used++;
390 : : else {
391 : 0 : used++;
392 : 0 : collided++;
393 : : }
394 : 0 : freq[c]++;
395 : : }
396 [ # # # # ]: 0 : for (i = nset; i > 0 && freq[i] == 0; i--);
397 [ # # ]: 0 : while (i >= 0) {
398 : 0 : fprintf(file, "pkg-hash: size %7d occurs %5d times\n", i, freq[i]);
399 : 0 : i--;
400 : : }
401 : 0 : fprintf(file, "pkg-hash: bins empty %d\n", empty);
402 : 0 : fprintf(file, "pkg-hash: bins used %d (collided %d)\n", used, collided);
403 : :
404 : 0 : m_output(file, "<hash report>");
405 : :
406 : 0 : free(freq);
407 : 0 : }
|
