1810873 - Assertion failure: aLength <= PLDHashTable::kMaxInitialLength, at /builds/worker/checkouts/gecko/xpcom/ds/PLDHashTable.cpp:147

Status: ASSIGNED

(Core :: Layout: Tables, defect)

Description

[Tyson Smith [:tsmith]]

Attachment: testcase.html

Found while fuzzing m-c 20221210-d4fa99ef8e6f (--enable-debug --enable-fuzzing)

To reproduce via Grizzly Replay:

$ pip install fuzzfetch grizzly-framework
$ python -m fuzzfetch -d --fuzzing -n firefox
$ python -m grizzly.replay ./firefox/firefox testcase.html

Assertion failure: aLength <= PLDHashTable::kMaxInitialLength, at /builds/worker/checkouts/gecko/xpcom/ds/PLDHashTable.cpp:147

#0 0x7fc60324f9ad in BestCapacity /builds/worker/checkouts/gecko/xpcom/ds/PLDHashTable.cpp:147:3
#1 0x7fc60324f9ad in PLDHashTable::ShrinkIfAppropriate() /builds/worker/checkouts/gecko/xpcom/ds/PLDHashTable.cpp:595:5
#2 0x7fc60324f57a in SearchTable<(PLDHashTable::SearchReason)0, (lambda at /builds/worker/checkouts/gecko/xpcom/ds/PLDHashTable.cpp:539:7), (lambda at /builds/worker/checkouts/gecko/xpcom/ds/PLDHashTable.cpp:543:7)> /builds/worker/checkouts/gecko/xpcom/ds/PLDHashTable.cpp
#3 0x7fc60324f57a in PLDHashTable::Remove(void const*) /builds/worker/checkouts/gecko/xpcom/ds/PLDHashTable.cpp:537:3
#4 0x7fc6089da50f in FreeByObjectID /builds/worker/workspace/obj-build/dist/include/mozilla/PresShell.h:290:5
#5 0x7fc6089da50f in nsCellMap::DestroyCellData(CellData*) /builds/worker/checkouts/gecko/layout/tables/nsCellMap.cpp:2381:32
#6 0x7fc6089d850c in nsCellMap::RebuildConsideringRows(nsTableCellMap&, int, nsTArray<nsTableRowFrame*>*, int) /builds/worker/checkouts/gecko/layout/tables/nsCellMap.cpp:2040:7
#7 0x7fc6089d7ff7 in nsTableCellMap::RebuildConsideringRows(nsCellMap*, int, nsTArray<nsTableRowFrame*>*, int, mozilla::TableArea&) /builds/worker/checkouts/gecko/layout/tables/nsCellMap.cpp:613:16
#8 0x7fc6089e945e in RemoveRows /builds/worker/checkouts/gecko/layout/tables/nsCellMap.cpp:473:16
#9 0x7fc6089e945e in nsTableFrame::RemoveRows(nsTableRowFrame&, int, bool) /builds/worker/checkouts/gecko/layout/tables/nsTableFrame.cpp:1000:14
#10 0x7fc608a0eb9f in nsTableRowGroupFrame::RemoveFrame(mozilla::FrameChildListID, nsIFrame*) /builds/worker/checkouts/gecko/layout/tables/nsTableRowGroupFrame.cpp:1546:17
#11 0x7fc60878104f in nsCSSFrameConstructor::ContentRemoved(nsIContent*, nsIContent*, nsCSSFrameConstructor::RemoveFlags) /builds/worker/checkouts/gecko/layout/base/nsCSSFrameConstructor.cpp:7587:5
#12 0x7fc60871f7c4 in mozilla::PresShell::ContentRemoved(nsIContent*, nsIContent*) /builds/worker/checkouts/gecko/layout/base/PresShell.cpp:4611:22
#13 0x7fc604e5c8ad in operator() /builds/worker/checkouts/gecko/dom/base/MutationObservers.cpp:196:3
#14 0x7fc604e5c8ad in Notify<(IsRemoval)1, (ShouldAssert)1, (lambda at /builds/worker/checkouts/gecko/dom/base/MutationObservers.cpp:196:3), (lambda at /builds/worker/checkouts/gecko/dom/base/MutationObservers.cpp:196:3)> /builds/worker/checkouts/gecko/dom/base/MutationObservers.cpp:91:5
#15 0x7fc604e5c8ad in mozilla::dom::MutationObservers::NotifyContentRemoved(nsINode*, nsIContent*, nsIContent*) /builds/worker/checkouts/gecko/dom/base/MutationObservers.cpp:197:3
#16 0x7fc604fe034f in nsINode::RemoveChildNode(nsIContent*, bool) /builds/worker/checkouts/gecko/dom/base/nsINode.cpp:2201:5
#17 0x7fc604d6d394 in mozilla::dom::Document::AdoptNode(nsINode&, mozilla::ErrorResult&) /builds/worker/checkouts/gecko/dom/base/Document.cpp:10105:17
#18 0x7fc60610688b in mozilla::dom::Document_Binding::adoptNode(JSContext*, JS::Handle<JSObject*>, void*, JSJitMethodCallArgs const&) /builds/worker/workspace/obj-build/dom/bindings/DocumentBinding.cpp:2287:60
#19 0x7fc6064a01f2 in bool mozilla::dom::binding_detail::GenericMethod<mozilla::dom::binding_detail::NormalThisPolicy, mozilla::dom::binding_detail::ThrowExceptions>(JSContext*, unsigned int, JS::Value*) /builds/worker/checkouts/gecko/dom/bindings/BindingUtils.cpp:3308:13
#20 0x7fc60a7fd556 in CallJSNative(JSContext*, bool (*)(JSContext*, unsigned int, JS::Value*), js::CallReason, JS::CallArgs const&) /builds/worker/checkouts/gecko/js/src/vm/Interpreter.cpp:459:13
#21 0x7fc60a7fce7f in js::InternalCallOrConstruct(JSContext*, JS::CallArgs const&, js::MaybeConstruct, js::CallReason) /builds/worker/checkouts/gecko/js/src/vm/Interpreter.cpp:547:12
#22 0x7fc60a7eeabf in CallFromStack /builds/worker/checkouts/gecko/js/src/vm/Interpreter.cpp:619:10
#23 0x7fc60a7eeabf in Interpret(JSContext*, js::RunState&) /builds/worker/checkouts/gecko/js/src/vm/Interpreter.cpp:3362:16
#24 0x7fc60a7e217e in js::RunScript(JSContext*, js::RunState&) /builds/worker/checkouts/gecko/js/src/vm/Interpreter.cpp:431:13
#25 0x7fc60a7fcd7b in js::InternalCallOrConstruct(JSContext*, JS::CallArgs const&, js::MaybeConstruct, js::CallReason) /builds/worker/checkouts/gecko/js/src/vm/Interpreter.cpp:579:13
#26 0x7fc60a7fe2ac in js::Call(JSContext*, JS::Handle<JS::Value>, JS::Handle<JS::Value>, js::AnyInvokeArgs const&, JS::MutableHandle<JS::Value>, js::CallReason) /builds/worker/checkouts/gecko/js/src/vm/Interpreter.cpp:646:8
#27 0x7fc60a8ba70c in JS::Call(JSContext*, JS::Handle<JS::Value>, JS::Handle<JS::Value>, JS::HandleValueArray const&, JS::MutableHandle<JS::Value>) /builds/worker/checkouts/gecko/js/src/vm/CallAndConstruct.cpp:117:10
#28 0x7fc606173071 in mozilla::dom::EventHandlerNonNull::Call(mozilla::dom::BindingCallContext&, JS::Handle<JS::Value>, mozilla::dom::Event&, JS::MutableHandle<JS::Value>, mozilla::ErrorResult&) /builds/worker/workspace/obj-build/dom/bindings/EventHandlerBinding.cpp:65:37
#29 0x7fc606a859f9 in void mozilla::dom::EventHandlerNonNull::Call<nsCOMPtr<mozilla::dom::EventTarget>>(nsCOMPtr<mozilla::dom::EventTarget> const&, mozilla::dom::Event&, JS::MutableHandle<JS::Value>, mozilla::ErrorResult&, char const*, mozilla::dom::CallbackObject::ExceptionHandling, JS::Realm*) /builds/worker/workspace/obj-build/dist/include/mozilla/dom/EventHandlerBinding.h:82:12
#30 0x7fc606a84be6 in mozilla::JSEventHandler::HandleEvent(mozilla::dom::Event*) /builds/worker/checkouts/gecko/dom/events/JSEventHandler.cpp:199:12
#31 0x7fc606a6556d in mozilla::EventListenerManager::HandleEventSubType(mozilla::EventListenerManager::Listener*, mozilla::dom::Event*, mozilla::dom::EventTarget*) /builds/worker/checkouts/gecko/dom/events/EventListenerManager.cpp:1314:22
#32 0x7fc606a661d9 in mozilla::EventListenerManager::HandleEventInternal(nsPresContext*, mozilla::WidgetEvent*, mozilla::dom::Event**, mozilla::dom::EventTarget*, nsEventStatus*, bool) /builds/worker/checkouts/gecko/dom/events/EventListenerManager.cpp:1504:17
#33 0x7fc606a5b046 in HandleEvent /builds/worker/checkouts/gecko/dom/events/EventListenerManager.h:395:5
#34 0x7fc606a5b046 in mozilla::EventTargetChainItem::HandleEvent(mozilla::EventChainPostVisitor&, mozilla::ELMCreationDetector&) /builds/worker/checkouts/gecko/dom/events/EventDispatcher.cpp:347:17
#35 0x7fc606a5a57b in mozilla::EventTargetChainItem::HandleEventTargetChain(nsTArray<mozilla::EventTargetChainItem>&, mozilla::EventChainPostVisitor&, mozilla::EventDispatchingCallback*, mozilla::ELMCreationDetector&) /builds/worker/checkouts/gecko/dom/events/EventDispatcher.cpp:549:16
#36 0x7fc606a5cd35 in mozilla::EventDispatcher::Dispatch(nsISupports*, nsPresContext*, mozilla::WidgetEvent*, mozilla::dom::Event*, nsEventStatus*, mozilla::EventDispatchingCallback*, nsTArray<mozilla::dom::EventTarget*>*) /builds/worker/checkouts/gecko/dom/events/EventDispatcher.cpp:1122:11
#37 0x7fc6087926d4 in nsDocumentViewer::LoadComplete(nsresult) /builds/worker/checkouts/gecko/layout/base/nsDocumentViewer.cpp:1079:7
#38 0x7fc609dccee0 in nsDocShell::EndPageLoad(nsIWebProgress*, nsIChannel*, nsresult) /builds/worker/checkouts/gecko/docshell/base/nsDocShell.cpp:6447:20
#39 0x7fc609dcc48b in nsDocShell::OnStateChange(nsIWebProgress*, nsIRequest*, unsigned int, nsresult) /builds/worker/checkouts/gecko/docshell/base/nsDocShell.cpp:5840:7
#40 0x7fc609dcdd86 in non-virtual thunk to nsDocShell::OnStateChange(nsIWebProgress*, nsIRequest*, unsigned int, nsresult) /builds/worker/checkouts/gecko/docshell/base/nsDocShell.cpp
#41 0x7fc60421a4e8 in nsDocLoader::DoFireOnStateChange(nsIWebProgress*, nsIRequest*, int&, nsresult) /builds/worker/checkouts/gecko/uriloader/base/nsDocLoader.cpp:1380:3
#42 0x7fc604219ad2 in nsDocLoader::doStopDocumentLoad(nsIRequest*, nsresult) /builds/worker/checkouts/gecko/uriloader/base/nsDocLoader.cpp:978:14
#43 0x7fc604217d65 in nsDocLoader::DocLoaderIsEmpty(bool, mozilla::Maybe<nsresult> const&) /builds/worker/checkouts/gecko/uriloader/base/nsDocLoader.cpp:797:9
#44 0x7fc604218f65 in nsDocLoader::OnStopRequest(nsIRequest*, nsresult) /builds/worker/checkouts/gecko/uriloader/base/nsDocLoader.cpp:680:5
#45 0x7fc609dffc7e in nsDocShell::OnStopRequest(nsIRequest*, nsresult) /builds/worker/checkouts/gecko/docshell/base/nsDocShell.cpp:13864:23
#46 0x7fc60350308f in mozilla::net::nsLoadGroup::NotifyRemovalObservers(nsIRequest*, nsresult) /builds/worker/checkouts/gecko/netwerk/base/nsLoadGroup.cpp:628:22
#47 0x7fc6035045b3 in mozilla::net::nsLoadGroup::RemoveRequest(nsIRequest*, nsISupports*, nsresult) /builds/worker/checkouts/gecko/netwerk/base/nsLoadGroup.cpp:532:10
#48 0x7fc604d761c9 in mozilla::dom::Document::DoUnblockOnload() /builds/worker/checkouts/gecko/dom/base/Document.cpp:11551:18
#49 0x7fc604d422eb in mozilla::dom::Document::UnblockOnload(bool) /builds/worker/checkouts/gecko/dom/base/Document.cpp:11489:9
#50 0x7fc604d5d008 in mozilla::dom::Document::DispatchContentLoadedEvents() /builds/worker/checkouts/gecko/dom/base/Document.cpp:8016:3
#51 0x7fc604e0d508 in applyImpl<mozilla::dom::Document, void (mozilla::dom::Document::*)()> /builds/worker/workspace/obj-build/dist/include/nsThreadUtils.h:1162:12
#52 0x7fc604e0d508 in apply<mozilla::dom::Document, void (mozilla::dom::Document::*)()> /builds/worker/workspace/obj-build/dist/include/nsThreadUtils.h:1168:12
#53 0x7fc604e0d508 in mozilla::detail::RunnableMethodImpl<mozilla::dom::Document*, void (mozilla::dom::Document::*)(), true, (mozilla::RunnableKind)0>::Run() /builds/worker/workspace/obj-build/dist/include/nsThreadUtils.h:1215:13
#54 0x7fc6032f0702 in mozilla::SchedulerGroup::Runnable::Run() /builds/worker/checkouts/gecko/xpcom/threads/SchedulerGroup.cpp:140:20
#55 0x7fc6032fa995 in mozilla::RunnableTask::Run() /builds/worker/checkouts/gecko/xpcom/threads/TaskController.cpp:539:16
#56 0x7fc6032f5f6c in mozilla::TaskController::DoExecuteNextTaskOnlyMainThreadInternal(mozilla::detail::BaseAutoLock<mozilla::Mutex&> const&) /builds/worker/checkouts/gecko/xpcom/threads/TaskController.cpp:852:26
#57 0x7fc6032f4b3a in mozilla::TaskController::ExecuteNextTaskOnlyMainThreadInternal(mozilla::detail::BaseAutoLock<mozilla::Mutex&> const&) /builds/worker/checkouts/gecko/xpcom/threads/TaskController.cpp:684:15
#58 0x7fc6032f4e95 in mozilla::TaskController::ProcessPendingMTTask(bool) /builds/worker/checkouts/gecko/xpcom/threads/TaskController.cpp:462:36
#59 0x7fc6032fe296 in operator() /builds/worker/checkouts/gecko/xpcom/threads/TaskController.cpp:188:37
#60 0x7fc6032fe296 in mozilla::detail::RunnableFunction<mozilla::TaskController::InitializeInternal()::$_2>::Run() /builds/worker/workspace/obj-build/dist/include/nsThreadUtils.h:546:5
#61 0x7fc603313b35 in nsThread::ProcessNextEvent(bool, bool*) /builds/worker/checkouts/gecko/xpcom/threads/nsThread.cpp:1197:16
#62 0x7fc60331a07d in NS_ProcessNextEvent(nsIThread*, bool) /builds/worker/checkouts/gecko/xpcom/threads/nsThreadUtils.cpp:473:10
#63 0x7fc603f10f23 in mozilla::ipc::MessagePump::Run(base::MessagePump::Delegate*) /builds/worker/checkouts/gecko/ipc/glue/MessagePump.cpp:85:21
#64 0x7fc603e32cd8 in MessageLoop::RunInternal() /builds/worker/checkouts/gecko/ipc/chromium/src/base/message_loop.cc:381:10
#65 0x7fc603e32be1 in RunHandler /builds/worker/checkouts/gecko/ipc/chromium/src/base/message_loop.cc:374:3
#66 0x7fc603e32be1 in MessageLoop::Run() /builds/worker/checkouts/gecko/ipc/chromium/src/base/message_loop.cc:356:3
#67 0x7fc608383938 in nsBaseAppShell::Run() /builds/worker/checkouts/gecko/widget/nsBaseAppShell.cpp:148:27
#68 0x7fc60a5b742b in XRE_RunAppShell() /builds/worker/checkouts/gecko/toolkit/xre/nsEmbedFunctions.cpp:743:20
#69 0x7fc603f11de9 in mozilla::ipc::MessagePumpForChildProcess::Run(base::MessagePump::Delegate*) /builds/worker/checkouts/gecko/ipc/glue/MessagePump.cpp:235:9
#70 0x7fc603e32cd8 in MessageLoop::RunInternal() /builds/worker/checkouts/gecko/ipc/chromium/src/base/message_loop.cc:381:10
#71 0x7fc603e32be1 in RunHandler /builds/worker/checkouts/gecko/ipc/chromium/src/base/message_loop.cc:374:3
#72 0x7fc603e32be1 in MessageLoop::Run() /builds/worker/checkouts/gecko/ipc/chromium/src/base/message_loop.cc:356:3
#73 0x7fc60a5b6f88 in XRE_InitChildProcess(int, char**, XREChildData const*) /builds/worker/checkouts/gecko/toolkit/xre/nsEmbedFunctions.cpp:676:34
#74 0x561767f14ca0 in content_process_main /builds/worker/checkouts/gecko/browser/app/../../ipc/contentproc/plugin-container.cpp:57:28
#75 0x561767f14ca0 in main /builds/worker/checkouts/gecko/browser/app/nsBrowserApp.cpp:359:18
#76 0x7fc617465d8f in __libc_start_call_main csu/../sysdeps/nptl/libc_start_call_main.h:58:16
#77 0x7fc617465e3f in __libc_start_main csu/../csu/libc-start.c:392:3
#78 0x561767eeb308 in _start (/home/user/workspace/browsers/m-c-20230116140954-fuzzing-debug/firefox-bin+0x5b308) (BuildId: 3c0a2e4948582c120895ff85171c1335af2e1568)

Comment 1

[Tyson Smith [:tsmith]]

A Pernosco session is available here: https://pernos.co/debug/3_NjwldBEBR_SIdw6fWCJA/index.html

Comment 2

[Bugmon [:jkratzer for issues]]

Verified bug as reproducible on mozilla-central 20230117161302-455aa95a34de.
Unable to bisect testcase (Testcase reproduces on start build!):

Start: 192e73e7c91313c09603efd1650931b917746bf4 (20220119093435)
End: d4fa99ef8e6f9c5ea1699a456c139c2bc12b797e (20221210092830)
BuildFlags: BuildFlags(asan=False, tsan=False, debug=True, fuzzing=True, coverage=False, valgrind=False, no_opt=False, fuzzilli=False, nyx=False)

Comment 3

[BugBot [:suhaib / :marco/ :calixte]]

The severity field is not set for this bug.
:dholbert, could you have a look please?

For more information, please visit auto_nag documentation.

Comment 4

[Daniel Holbert [:dholbert]]

Yeah, S3 seems appropriate. Looking in pernosco, this is an assertion failure where we're resizing a hash table (and the hash table is only used in builds with MOZ_DIAGNOSTIC_ASSERT_ENABLED i.e. early-beta-and-earlier).

So: Firefox release versions aren't affected, for multiple reasons (debug-only assertion, in early-beta-and-earlier-guarded diagnostic code).

The assertion itself seems benign. We've just done a removal from the hash table, and we're considering whether we should shrink the table; and the existing size is larger than the logic can handle. (The existing size -- i.e. PLDHashTable::mEntryCount, passed as the aLength arg to BestCapacity -- is 39969025 which is greater than PLDHashTable::kMaxInitialLength which is 33554432.

(I'm not sure why kMaxInitialLength is a magic value here -- I suspect it's just to have some breathing room so that our multiplication here is safely several orders of magnitude away from overflowing.)

Comment 5

[Daniel Holbert [:dholbert]]

So the proximal issue of the assertion-saying-the-length-is-too-big: the assertion has a note saying that we should check for the length in the caller:
https://searchfox.org/mozilla-central/rev/9dfda5ccb0fc42d7666a54b1caf1af6525e49694/xpcom/ds/PLDHashTable.cpp#144-147

static inline void BestCapacity(uint32_t aLength, uint32_t* aCapacityOut,
                                uint32_t* aLog2CapacityOut) {
  // Callers should ensure this is true.
  MOZ_ASSERT(aLength <= PLDHashTable::kMaxInitialLength);

The caller here is another PLDHashTable function, ShrinkIfAppropriate. Maybe that function should decline to call BestCapacity if mEntryCount is sufficiently high?

Behind that proximal issue: is it expected that the length so large in the first place? The answer is basically "yes". It's so large because this hash set is keeping track of all presshell arena-allocated objects, including "CellData objects", and we've got quite a lot of those. nsCellMap::AppendCell has a section that does Create CellData objects for the rows that this cell spans:
https://searchfox.org/mozilla-central/rev/9dfda5ccb0fc42d7666a54b1caf1af6525e49694/layout/tables/nsCellMap.cpp#1361-1362,1397

// Create CellData objects for the rows that this cell spans. Set
// their mOrigCell to nullptr and their mSpanData to point to data.
...
        cellData = AllocCellData(nullptr);

...which as quoted here, seems to mean calling AllocCellData for all of the spanned cells. And this fuzzer-testcase has a cell with colspan="16384" rowspan="29812" which spans quite a lot of cells, which means we do lots of AllocCellData.

It's not quite 16384*29812 cells, since we have upper limits on the max rowspan and colspan values, defined here:
https://searchfox.org/mozilla-central/rev/9dfda5ccb0fc42d7666a54b1caf1af6525e49694/layout/tables/nsITableCellLayout.h#10-12

#define MAX_ROWSPAN 65534  // the cellmap can not handle more.
#define MAX_COLSPAN \
  1000  // limit as IE and opera do.  If this ever changes,

Our colspan value is larger than that 1000 limit, so we effectively have colspan="1000". So we have 1000 * 29812 = 29,812,000 cells. And presumably we get around that number of AllocCellData calls, which is what gets us close enough to the aforementioned PLDHashTable::kMaxInitialLength value of 33,554,432.

With some additional pres-shell arena-allocated objects, we easily overshoot that value and fail this bug's assertion.

So: summing up, given how our CellData stuff works, it's expected that we do this number of allocations and inflate this diagnostic hash-set accordingly. And we perhaps need to just adjust the hashtable ShrinkIfAppropriate function so that it doesn't try to shrink if it knows it's going to trip over this assertion.

Comment 6

[Daniel Holbert [:dholbert]]

side note: bug 1530311 is where this PLDHashTable.cpp assertion was added -- though per the end of bug 1530311 comment 2, it seems it wasn't actually a problem for PLDHashTable, and the assertion was probably just added for consistency with the MFBT HashTable (which was affected by the bug being fixed there), AFAICT.

Comment 7

[Daniel Holbert [:dholbert]]

Also: I'm going to mark this as "in-testsuite:-" since I don't think it's possible to add an efficient testcase here, unfortunately. The testcase takes tens of seconds on debug+opt builds on my fast system (before and after this is fixed), and it's probably not a good use of resources to check in a crashtest that takes that long on every testrun, just to find out whether it asserts or passes at the end of that tens-of-seconds hang. And given the nature of the issue, I don't think we could adjust the testcase to make it faster and also make it exercise the codepath that would've tripped this assertion.

Comment 8

[Daniel Holbert [:dholbert]]

Attachment: Bug 1810873: Change PLDHashTable::ShrinkIfAppropriate to respect BestCapacity's precondition. r?nika,mccr8

This patch shouldn't change user-observable behavior. The only behavioral
difference here is that we'll be more hesitant to shrink absurdly-large
PLDHashTable instances, when they have an entry removed. We will still be able
to shrink it eventually, but more removals may be required before we do so. It
seems this caution is necessary, in order to ensure we satisfy the precondition
in BestCapacity(), so that it can confidently compute an appropriate new
capacity for us without being worried about integer overflow or issues like
that.

Comment 9

[Bugmon [:jkratzer for issues]]

Unable to reproduce bug 1810873 using build mozilla-central 20221210092830-d4fa99ef8e6f. Without a baseline, bugmon is unable to analyze this bug.
Removing bugmon keyword as no further action possible. Please review the bug and re-add the keyword for further analysis.