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 *
pkg_hash_find_set(const char * inname)68 pkg_hash_find_set(const char *inname)
69 {
70 struct pkgset **setp, *new_set;
71 char *name = m_strdup(inname), *p;
72
73 p= name;
74 while (*p) {
75 *p = c_tolower(*p);
76 p++;
77 }
78
79 setp = bins + (str_fnv_hash(name) % (BINS));
80 while (*setp && strcasecmp((*setp)->name, name))
81 setp = &(*setp)->next;
82 if (*setp) {
83 free(name);
84 return *setp;
85 }
86
87 new_set = nfmalloc(sizeof(*new_set));
88 pkgset_blank(new_set);
89 new_set->name = nfstrsave(name);
90 new_set->next = NULL;
91 *setp = new_set;
92 nset++;
93 npkg++;
94
95 free(name);
96
97 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 *
pkg_hash_get_singleton(struct pkgset * set)112 pkg_hash_get_singleton(struct pkgset *set)
113 {
114 struct pkginfo *pkg;
115
116 switch (pkgset_installed_instances(set)) {
117 case 0:
118 /* Pick an available candidate. */
119 for (pkg = &set->pkg; pkg; pkg = pkg->arch_next) {
120 const struct dpkg_arch *arch = pkg->available.arch;
121
122 if (arch->type == DPKG_ARCH_NATIVE || arch->type == DPKG_ARCH_ALL)
123 return pkg;
124 }
125 /* Or failing that, the first entry. */
126 return &set->pkg;
127 case 1:
128 for (pkg = &set->pkg; pkg; pkg = pkg->arch_next) {
129 if (pkg->status > PKG_STAT_NOTINSTALLED)
130 return pkg;
131 }
132 internerr("pkgset '%s' should have one installed instance", set->name);
133 default:
134 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 *
pkg_hash_find_singleton(const char * name)146 pkg_hash_find_singleton(const char *name)
147 {
148 struct pkgset *set;
149 struct pkginfo *pkg;
150
151 set = pkg_hash_find_set(name);
152 pkg = pkg_hash_get_singleton(set);
153 if (pkg == NULL)
154 ohshit(_("ambiguous package name '%s' with more "
155 "than one installed instance"), set->name);
156
157 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 *
pkg_hash_get_pkg(struct pkgset * set,const struct dpkg_arch * arch)174 pkg_hash_get_pkg(struct pkgset *set, const struct dpkg_arch *arch)
175 {
176 struct pkginfo *pkg, **pkgp;
177
178 if (arch == NULL)
179 internerr("arch argument is NULL");
180 if (arch->type == DPKG_ARCH_NONE)
181 internerr("arch argument is none");
182
183 pkg = &set->pkg;
184
185 /* If there's a single unused slot, let's use that. */
186 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 pkg->installed.arch = arch;
190 pkg->available.arch = arch;
191 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 for (pkgp = &pkg; *pkgp; pkgp = &(*pkgp)->arch_next) {
198 if ((*pkgp)->installed.arch == arch)
199 return *pkgp;
200 }
201
202 /* Need to create a new instance for the wanted architecture. */
203 pkg = nfmalloc(sizeof(*pkg));
204 pkg_blank(pkg);
205 pkg->set = set;
206 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 pkg->installed.arch = arch;
210 pkg->available.arch = arch;
211 *pkgp = pkg;
212 npkg++;
213
214 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 *
pkg_hash_find_pkg(const char * name,const struct dpkg_arch * arch)226 pkg_hash_find_pkg(const char *name, const struct dpkg_arch *arch)
227 {
228 struct pkgset *set;
229 struct pkginfo *pkg;
230
231 set = pkg_hash_find_set(name);
232 pkg = pkg_hash_get_pkg(set, arch);
233
234 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
pkg_hash_count_set(void)243 pkg_hash_count_set(void)
244 {
245 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
pkg_hash_count_pkg(void)254 pkg_hash_count_pkg(void)
255 {
256 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 *
pkg_hash_iter_new(void)272 pkg_hash_iter_new(void)
273 {
274 struct pkg_hash_iter *iter;
275
276 iter = m_malloc(sizeof(*iter));
277 iter->pkg = NULL;
278 iter->nbinn = 0;
279
280 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 *
pkg_hash_iter_next_set(struct pkg_hash_iter * iter)293 pkg_hash_iter_next_set(struct pkg_hash_iter *iter)
294 {
295 struct pkgset *set;
296
297 while (!iter->pkg) {
298 if (iter->nbinn >= BINS)
299 return NULL;
300 if (bins[iter->nbinn])
301 iter->pkg = &bins[iter->nbinn]->pkg;
302 iter->nbinn++;
303 }
304
305 set = iter->pkg->set;
306 if (set->next)
307 iter->pkg = &set->next->pkg;
308 else
309 iter->pkg = NULL;
310
311 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 *
pkg_hash_iter_next_pkg(struct pkg_hash_iter * iter)328 pkg_hash_iter_next_pkg(struct pkg_hash_iter *iter)
329 {
330 struct pkginfo *pkg;
331
332 while (!iter->pkg) {
333 if (iter->nbinn >= BINS)
334 return NULL;
335 if (bins[iter->nbinn])
336 iter->pkg = &bins[iter->nbinn]->pkg;
337 iter->nbinn++;
338 }
339
340 pkg = iter->pkg;
341 if (pkg->arch_next)
342 iter->pkg = pkg->arch_next;
343 else if (pkg->set->next)
344 iter->pkg = &pkg->set->next->pkg;
345 else
346 iter->pkg = NULL;
347
348 return pkg;
349 }
350
351 /**
352 * Free the package database iterator.
353 *
354 * @name iter The iterator.
355 */
356 void
pkg_hash_iter_free(struct pkg_hash_iter * iter)357 pkg_hash_iter_free(struct pkg_hash_iter *iter)
358 {
359 free(iter);
360 }
361
362 void
pkg_hash_reset(void)363 pkg_hash_reset(void)
364 {
365 int i;
366
367 dpkg_arch_reset_list();
368 nffreeall();
369 nset = 0;
370 npkg = 0;
371 for (i=0; i<BINS; i++) bins[i]= NULL;
372 }
373
374 void
pkg_hash_report(FILE * file)375 pkg_hash_report(FILE *file)
376 {
377 int i, c;
378 struct pkgset *pkg;
379 int *freq;
380 int empty = 0, used = 0, collided = 0;
381
382 freq = m_malloc(sizeof(int) * nset + 1);
383 for (i = 0; i <= nset; i++)
384 freq[i] = 0;
385 for (i=0; i<BINS; i++) {
386 for (c=0, pkg= bins[i]; pkg; c++, pkg= pkg->next);
387 fprintf(file, "pkg-hash: bin %5d has %7d\n", i, c);
388 if (c == 0)
389 empty++;
390 else if (c == 1)
391 used++;
392 else {
393 used++;
394 collided++;
395 }
396 freq[c]++;
397 }
398 for (i = nset; i > 0 && freq[i] == 0; i--);
399 while (i >= 0) {
400 fprintf(file, "pkg-hash: size %7d occurs %5d times\n", i, freq[i]);
401 i--;
402 }
403 fprintf(file, "pkg-hash: bins empty %d\n", empty);
404 fprintf(file, "pkg-hash: bins used %d (collided %d)\n", used, collided);
405
406 m_output(file, "<hash report>");
407
408 free(freq);
409 }
410