pidgin-0001: add_all_buddies_to_permit_list O(B^2) GSList scan

Target

Pidgin 2.14.x (libpurple)

Severity

MEDIUM

MOAD

0001 (CWE-407: Inefficient Algorithmic Complexity)

Location

libpurple/privacy.c — add_all_buddies_to_permit_list()

Called from:

purple_privacy_allow() when switching from ALLOW_BUDDYLIST mode
purple_privacy_deny() when switching from ALLOW_BUDDYLIST mode

Description

add_all_buddies_to_permit_list() synchronizes our account's permit (allow) list with our buddy list. It calls purple_find_buddies(account, NULL) to get all B buddies, then iterates them. For each buddy it calls:

g_slist_find_custom(account->permit, name, (GCompareFunc)g_utf8_collate)

account->permit is a GSList. As buddies are added to our permit list, our list grows to size B. Each subsequent g_slist_find_custom scans more of our growing list. Total comparisons: 0 + 1 + 2 + ... + (B-1) = O(B^2/2).

With a large buddy list (e.g. 1000 contacts), switching privacy modes triggers 499,500 string comparisons instead of 1,000.

Fix

Before our buddy iteration loop, snapshot account->permit into a GHashTable for O(1) membership tests. Replace g_slist_find_custom() with g_hash_table_lookup(). Destroy our snapshot hash table after our loop.

Speedup

B (buddies)	Defective ops	Fixed ops	Ratio
100	4,950	100	49.5x
500	124,750	500	249.5x
1,000	499,500	1,000	499.5x
2,000	1,999,000	2,000	999.5x

Also noted in blist.c

purple_group_get_accounts() and purple_blist_remove_account() use the same O(N^2) dedup-accumulate pattern with g_slist_find / g_list_find. These are lower severity (accounts per group is typically 1-5) but share our root cause.

MOAD-0002 (Intertangle)

libpurple/blist.c: purplebuddylist, buddies_cache, groups_cache are global mutable singletons accessed by all protocol callbacks. No mutex. Architectural intertangle; not a single-function patch.

MOAD-0003

CLEAN. Pidgin is C/GLib main-loop single-threaded. No ThreadLocal or GPrivate request-scoped identity leakage found.

MOAD-0005

CLEAN. Single-threaded GLib event loop; no concurrent cache-get+put races.

2.2 KiB Raw Permalink Blame History