Hashtable Adventures

[derrod]

Description

This is a finished implementation of @jp9000's hash-table branch.

Overview: Switched various components from using linked lists or radix/trie trees to hashmaps (via uthash):

• Config file utility (INI read/write)
• Hotkeys and their name map
• OBS data (obs_data_item)
• Translation text lookup (lookup_t)
• Public sources
• Properties

Breaking changes

• N/A

Potentially breaking changes

• obs_source_create() now deduplicates the provided name for public sources
  • Also affects obs_source_duplicate() and obs_source_set_name()
  • This makes the functions behave as they are described in the documentation, however, some people may rely on the previous behaviour
• Private groups are no longer enumerated in obs_enum_sources()
  • OBS itself does not create groups as private sources
• config_t is now case-sensitive
  • Only example I found was SysTrayEnabled in window-basic-main.cpp, this has been fixed in this PR
• text_lookup is now case-sensitive
  • The only issue I could find in OBS itself was obs-ffmpeg-source.c using an incorrectly-capitalised translation key for the name (FFMpegSource), this has been fixed in this PR

Motivation and Context

Faster and nicer code. Especially for translation lookups (10x speedup in my tests).

How Has This Been Tested?

• Launched OBS
• Made some changes to config/sources
• Checked there are no memory leaks

Types of changes

• Code cleanup (non-breaking change which makes code smaller or more readable)
• Breaking change (fix or feature that would cause existing functionality to change)

Checklist:

• [x] My code has been run through clang-format.
• [x] I have read the contributing document.
• [x] My code is not on the master branch.
• [x] The code has been tested.
• [x] All commit messages are properly formatted and commits squashed where appropriate.
• [x] I have included updates to all appropriate documentation.

[tytan652]

uthash (headers only library) deps should be added to obs-deps. Ubuntu has the uthash-dev package.

[derrod]

uthash (headers only library) deps should be added to obs-deps. Ubuntu has the uthash-dev package.

The version in ubuntu 20.04 is older and is missing some stuff. I think for something as fundamental and small as this vendoring it inside libobs itself like SIMDe might be the most sensible choice since we really only need the uthash.h file. Unless we want to use it in plugins of course.

[tytan652]

Moved to review

[kkartaltepe]

Unless we want to use it in plugins of course.

I would like to use this in xcomposite to replace our poor implementation of a set. But also agree with just keeping the header in-project.

[derrod]

I would like to use this in xcomposite to replace our poor implementation of a set. But also agree with just keeping the header in-project.

In that case I could move it back to deps. That would also make it easier to update in the future since you just need to replace the header files there with the latest release.

I also don't know if we care about Elbrus CPU support still, but that would require using the uthash version from git since their latest release doesn't have the fix for that yet (https://github.com/troydhanson/uthash/commit/4d01591ed9b67ff153410d0f0cfa47f51b735eb4).

[derrod]

Just for fun, a little test to use xxHash with SSE2 vector instructions instead of uthash's built-in hash functions: https://github.com/derrod/obs-studio/commit/0fb32c56f06e21f31ccee69ac9eb7d1f2e2c2b29 (obs-deps commit to add it for Windows here: https://github.com/derrod/obs-deps/commit/befd6564ae659fca586927f9d0e43430131bb94b).

It's a decent bit faster (~25%) but probably overkill for our purposes. Just felt like leaving it here since it's an interesting experiment.

[derrod]

Moved hotkeys to hashtables, this is one of the things where you can see an absolutely massive improvement when it comes to saving/closing a scene collection. In particular the example linked in #6081 (Massive.json) on my system now takes < 1 second to unload/save, down from over 1 minute and 15 seconds!

[norihiro]

Can we add HASH_ITER to ForEachMacros in .clang-format?

diff --git a/.clang-format b/.clang-format
index c9dfc48e9..89cbc19a6 100644
--- a/.clang-format
+++ b/.clang-format
@@ -55,10 +55,11 @@ DisableFormat: false
 FixNamespaceComments: false
 ForEachMacros: 
   - 'json_object_foreach'
   - 'json_object_foreach_safe'
   - 'json_array_foreach'
+  - 'HASH_ITER'
 IncludeBlocks: Preserve
 IndentCaseLabels: false
 IndentPPDirectives: None
 IndentWidth: 8
 IndentWrappedFunctionNames: false

[derrod]

We can, yeah. Not sure I like the result more than the default but it's fine:

Edit: Added that now in https://github.com/obsproject/obs-studio/pull/8229/commits/32c725dcf1e4b10a806e7a9bc2069f48d09c8016

[derrod]

As a general note, some of these commits could be squashed, but I'd prefer #8345 to be merged beforehand so I only have to resolve conflicts once (as a bonus the diff will be slightly cleaner if this is applied on top of 8345 than the other way around).

[derrod]

As mentioned in the previous comment I'd prefer if #8345 is merged first and to that effect I have now rebased this PR on that one and drafted it until its merged. This makes a few things slightly easier/cleaner. There also were a number of minor changes and code cleanup compared to the original PR.

[derrod]

With #8345 merged I updated and cleaned up this PR a bit. I'm now fairly happy with where it's at. Hopefully it can make it for 29.1!

[norihiro]

I got a crash at exit saying double free or corruption (out).

I tried to reproduce this without 3rd party plugin but I couldn't do that so far.

obs-studio commit: 67c93f43 OBS log: https://obsproject.com/logs/Mx4I5sOo1TwCfdb3 3rd party plugin: obs-ptz commit c904d0391

Steps: 0. Build and install obs-ptz plugin.

1. Start OBS
2. Add a dock PTZ Controls
3. Continue stop and start OBS until the crash happen. (roughly once for 10 times)

[Current thread is 1 (Thread 0x7fe732c9c480 (LWP 422197))]
(gdb) bt
#0  0x00007fe73df8e490 in unregister_hotkey (id=id@entry=24) at /home/kamae/repo/obs-studio/libobs/obs-hotkey.c:914
#1  0x00007fe73df9191d in obs_hotkey_unregister (id=24) at /home/kamae/repo/obs-studio/libobs/obs-hotkey.c:956
#2  0x00007fe6a927ba8b in PTZControls::~PTZControls() (this=0x2689c40, __in_chrg=<optimized out>)
    at /home/kamae/repo/obs-ptz/src/ptz-controls.cpp:296
#3  0x00007fe6a927bb69 in PTZControls::~PTZControls() (this=0x2689c40, __in_chrg=<optimized out>)
    at /home/kamae/repo/obs-ptz/src/ptz-controls.cpp:301
#4  0x00007fe73bdab75a in QObjectPrivate::deleteChildren() () at /lib64/libQt6Core.so.6
#5  0x00007fe73d20d4b8 in QWidget::~QWidget() () at /lib64/libQt6Widgets.so.6
#6  0x000000000053baa9 in OBSBasic::~OBSBasic() (this=0xf5f040, __in_chrg=<optimized out>)
    at /home/kamae/repo/obs-studio/UI/window-basic-main.cpp:2787
#7  0x00007fe73bda3693 in QObject::event(QEvent*) () at /lib64/libQt6Core.so.6
#8  0x00007fe73d1b9a35 in QApplicationPrivate::notify_helper(QObject*, QEvent*) () at /lib64/libQt6Widgets.so.6
#9  0x00007fe73bd50c48 in QCoreApplication::notifyInternal2(QObject*, QEvent*) () at /lib64/libQt6Core.so.6
#10 0x00007fe73bd53f94 in QCoreApplicationPrivate::sendPostedEvents(QObject*, int, QThreadData*) () at /lib64/libQt6Core.so.6
#11 0x00007fe73c00a147 in postEventSourceDispatch(_GSource*, int (*)(void*), void*) () at /lib64/libQt6Core.so.6
#12 0x00007fe73b318faf in g_main_context_dispatch () at /lib64/libglib-2.0.so.0
#13 0x00007fe73b36e2c8 in g_main_context_iterate.constprop () at /lib64/libglib-2.0.so.0
#14 0x00007fe73b316940 in g_main_context_iteration () at /lib64/libglib-2.0.so.0
#15 0x00007fe73c009a10 in QEventDispatcherGlib::processEvents(QFlags<QEventLoop::ProcessEventsFlag>) () at /lib64/libQt6Core.so.6
#16 0x00007fe73bd5da1b in QEventLoop::exec(QFlags<QEventLoop::ProcessEventsFlag>) () at /lib64/libQt6Core.so.6
#17 0x00007fe73bd59118 in QCoreApplication::exec() () at /lib64/libQt6Core.so.6
#18 0x000000000046996a in run_program (argv=0x7ffeee641088, argc=<optimized out>, logFile=...)
    at /home/kamae/repo/obs-studio/UI/obs-app.cpp:2484
#19 main(int, char**) (argc=<optimized out>, argv=0x7ffeee641088) at /home/kamae/repo/obs-studio/UI/obs-app.cpp:3376

When I have more plugins, I saw a crash at another location. obs-studio commit: 67c93f43 OBS log: https://obsproject.com/logs/1Cwh5KCeF6vlQsEw

backtrace:

Program terminated with signal SIGABRT, Aborted.
#0  0x00007f060228ebec in __pthread_kill_implementation () from /lib64/libc.so.6
[Current thread is 1 (Thread 0x7f05dbfff640 (LWP 412422))]
(gdb) bt
#0  0x00007f060228ebec in __pthread_kill_implementation () at /lib64/libc.so.6
#1  0x00007f060223e956 in raise () at /lib64/libc.so.6
#2  0x00007f06022287f4 in abort () at /lib64/libc.so.6
#3  0x00007f0602282d3e in __libc_message () at /lib64/libc.so.6
#4  0x00007f060229893c in  () at /lib64/libc.so.6
#5  0x00007f060229aa60 in _int_free () at /lib64/libc.so.6
#6  0x00007f060229d133 in free () at /lib64/libc.so.6
#7  0x00007f0604d8eadb in a_free (ptr=<optimized out>) at /home/kamae/repo/obs-studio/libobs/util/bmem.c:84
#8  0x00007f0604d2d707 in unregister_hotkey (id=59) at /home/kamae/repo/obs-studio/libobs/obs-hotkey.c:930
#9  0x00007f0604d30c01 in context_release_hotkeys (context=0x382c920) at /home/kamae/repo/obs-studio/libobs/obs-hotkey.c:979
#10 obs_hotkeys_context_release (context=0x382c920) at /home/kamae/repo/obs-studio/libobs/obs-hotkey.c:1002
#11 0x00007f0604d1bc3e in obs_context_data_free (context=context@entry=0x382c920) at /home/kamae/repo/obs-studio/libobs/obs.c:2537
#12 0x00007f0604d553a8 in obs_source_destroy_defer (source=0x382c920) at /home/kamae/repo/obs-studio/libobs/obs-source.c:779
#13 0x00007f0604d9c838 in tiny_tubular_task_thread (param=0x235dfe0) at /home/kamae/repo/obs-studio/libobs/util/task.c:161
#14 0x00007f060228cdcd in start_thread () at /lib64/libc.so.6
#15 0x00007f0602312630 in clone3 () at /lib64/libc.so.6

At the trace #12, the ID of the source is pulse_input_capture.

[derrod]

Rebased on master and fixed the use-after-free @norihiro pointed out. Also ran it with AddressSanitizer just to see if it would catch anything else, but it didn't (it just made running OBS nearly unbearable on my machine).