1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
2 * vim: set ts=8 sts=4 et sw=4 tw=99:
3 * This Source Code Form is subject to the terms of the Mozilla Public
4 * License, v. 2.0. If a copy of the MPL was not distributed with this
5 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
6
7 /*
8 * JS atom table.
9 */
10
11 #include "jsatominlines.h"
12
13 #include "mozilla/ArrayUtils.h"
14 #include "mozilla/RangedPtr.h"
15
16 #include <string.h>
17
18 #include "jscntxt.h"
19 #include "jsstr.h"
20 #include "jstypes.h"
21
22 #include "gc/Marking.h"
23 #include "vm/Symbol.h"
24 #include "vm/Xdr.h"
25
26 #include "jscntxtinlines.h"
27 #include "jscompartmentinlines.h"
28 #include "jsobjinlines.h"
29
30 #include "vm/String-inl.h"
31
32 using namespace js;
33 using namespace js::gc;
34
35 using mozilla::ArrayEnd;
36 using mozilla::ArrayLength;
37 using mozilla::RangedPtr;
38
39 const char*
AtomToPrintableString(ExclusiveContext * cx,JSAtom * atom,JSAutoByteString * bytes)40 js::AtomToPrintableString(ExclusiveContext* cx, JSAtom* atom, JSAutoByteString* bytes)
41 {
42 JSString* str = QuoteString(cx, atom, 0);
43 if (!str)
44 return nullptr;
45 return bytes->encodeLatin1(cx, str);
46 }
47
48 #define DEFINE_PROTO_STRING(name,code,init,clasp) const char js_##name##_str[] = #name;
49 JS_FOR_EACH_PROTOTYPE(DEFINE_PROTO_STRING)
50 #undef DEFINE_PROTO_STRING
51
52 #define CONST_CHAR_STR(idpart, id, text) const char js_##idpart##_str[] = text;
53 FOR_EACH_COMMON_PROPERTYNAME(CONST_CHAR_STR)
54 #undef CONST_CHAR_STR
55
56 /* Constant strings that are not atomized. */
57 const char js_break_str[] = "break";
58 const char js_case_str[] = "case";
59 const char js_catch_str[] = "catch";
60 const char js_class_str[] = "class";
61 const char js_const_str[] = "const";
62 const char js_continue_str[] = "continue";
63 const char js_debugger_str[] = "debugger";
64 const char js_default_str[] = "default";
65 const char js_do_str[] = "do";
66 const char js_else_str[] = "else";
67 const char js_enum_str[] = "enum";
68 const char js_export_str[] = "export";
69 const char js_extends_str[] = "extends";
70 const char js_finally_str[] = "finally";
71 const char js_for_str[] = "for";
72 const char js_getter_str[] = "getter";
73 const char js_if_str[] = "if";
74 const char js_implements_str[] = "implements";
75 const char js_import_str[] = "import";
76 const char js_in_str[] = "in";
77 const char js_instanceof_str[] = "instanceof";
78 const char js_interface_str[] = "interface";
79 const char js_package_str[] = "package";
80 const char js_private_str[] = "private";
81 const char js_protected_str[] = "protected";
82 const char js_public_str[] = "public";
83 const char js_send_str[] = "send";
84 const char js_setter_str[] = "setter";
85 const char js_switch_str[] = "switch";
86 const char js_this_str[] = "this";
87 const char js_try_str[] = "try";
88 const char js_typeof_str[] = "typeof";
89 const char js_void_str[] = "void";
90 const char js_while_str[] = "while";
91 const char js_with_str[] = "with";
92
93 // Use a low initial capacity for atom hash tables to avoid penalizing runtimes
94 // which create a small number of atoms.
95 static const uint32_t JS_STRING_HASH_COUNT = 64;
96
readonlyThreadsafeLookup(const AtomSet::Lookup & l) const97 AtomSet::Ptr js::FrozenAtomSet::readonlyThreadsafeLookup(const AtomSet::Lookup& l) const {
98 return mSet->readonlyThreadsafeLookup(l);
99 }
100
101 struct CommonNameInfo
102 {
103 const char* str;
104 size_t length;
105 };
106
107 bool
initializeAtoms(JSContext * cx)108 JSRuntime::initializeAtoms(JSContext* cx)
109 {
110 atoms_ = cx->new_<AtomSet>();
111 if (!atoms_ || !atoms_->init(JS_STRING_HASH_COUNT))
112 return false;
113
114 // |permanentAtoms| hasn't been created yet.
115 MOZ_ASSERT(!permanentAtoms);
116
117 if (parentRuntime) {
118 staticStrings = parentRuntime->staticStrings;
119 commonNames = parentRuntime->commonNames;
120 emptyString = parentRuntime->emptyString;
121 permanentAtoms = parentRuntime->permanentAtoms;
122 wellKnownSymbols = parentRuntime->wellKnownSymbols;
123 return true;
124 }
125
126 staticStrings = cx->new_<StaticStrings>();
127 if (!staticStrings || !staticStrings->init(cx))
128 return false;
129
130 static const CommonNameInfo cachedNames[] = {
131 #define COMMON_NAME_INFO(idpart, id, text) { js_##idpart##_str, sizeof(text) - 1 },
132 FOR_EACH_COMMON_PROPERTYNAME(COMMON_NAME_INFO)
133 #undef COMMON_NAME_INFO
134 #define COMMON_NAME_INFO(name, code, init, clasp) { js_##name##_str, sizeof(#name) - 1 },
135 JS_FOR_EACH_PROTOTYPE(COMMON_NAME_INFO)
136 #undef COMMON_NAME_INFO
137 };
138
139 commonNames = cx->new_<JSAtomState>();
140 if (!commonNames)
141 return false;
142
143 ImmutablePropertyNamePtr* names = reinterpret_cast<ImmutablePropertyNamePtr*>(commonNames);
144 for (size_t i = 0; i < ArrayLength(cachedNames); i++, names++) {
145 JSAtom* atom = Atomize(cx, cachedNames[i].str, cachedNames[i].length, PinAtom);
146 if (!atom)
147 return false;
148 names->init(atom->asPropertyName());
149 }
150 MOZ_ASSERT(uintptr_t(names) == uintptr_t(commonNames + 1));
151
152 emptyString = commonNames->empty;
153
154 // Create the well-known symbols.
155 wellKnownSymbols = cx->new_<WellKnownSymbols>();
156 if (!wellKnownSymbols)
157 return false;
158
159 ImmutablePropertyNamePtr* descriptions = commonNames->wellKnownSymbolDescriptions();
160 ImmutableSymbolPtr* symbols = reinterpret_cast<ImmutableSymbolPtr*>(wellKnownSymbols);
161 for (size_t i = 0; i < JS::WellKnownSymbolLimit; i++) {
162 JS::Symbol* symbol = JS::Symbol::new_(cx, JS::SymbolCode(i), descriptions[i]);
163 if (!symbol) {
164 ReportOutOfMemory(cx);
165 return false;
166 }
167 symbols[i].init(symbol);
168 }
169
170 return true;
171 }
172
173 void
finishAtoms()174 JSRuntime::finishAtoms()
175 {
176 js_delete(atoms_);
177
178 if (!parentRuntime) {
179 js_delete(staticStrings);
180 js_delete(commonNames);
181 js_delete(permanentAtoms);
182 js_delete(wellKnownSymbols);
183 }
184
185 atoms_ = nullptr;
186 staticStrings = nullptr;
187 commonNames = nullptr;
188 permanentAtoms = nullptr;
189 wellKnownSymbols = nullptr;
190 emptyString = nullptr;
191 }
192
193 void
MarkAtoms(JSTracer * trc)194 js::MarkAtoms(JSTracer* trc)
195 {
196 JSRuntime* rt = trc->runtime();
197 for (AtomSet::Enum e(rt->atoms()); !e.empty(); e.popFront()) {
198 const AtomStateEntry& entry = e.front();
199 if (!entry.isPinned())
200 continue;
201
202 JSAtom* atom = entry.asPtrUnbarriered();
203 TraceRoot(trc, &atom, "interned_atom");
204 MOZ_ASSERT(entry.asPtrUnbarriered() == atom);
205 }
206 }
207
208 void
MarkPermanentAtoms(JSTracer * trc)209 js::MarkPermanentAtoms(JSTracer* trc)
210 {
211 JSRuntime* rt = trc->runtime();
212
213 // Permanent atoms only need to be marked in the runtime which owns them.
214 if (rt->parentRuntime)
215 return;
216
217 // Static strings are not included in the permanent atoms table.
218 if (rt->staticStrings)
219 rt->staticStrings->trace(trc);
220
221 if (rt->permanentAtoms) {
222 for (FrozenAtomSet::Range r(rt->permanentAtoms->all()); !r.empty(); r.popFront()) {
223 const AtomStateEntry& entry = r.front();
224
225 JSAtom* atom = entry.asPtr();
226 TraceProcessGlobalRoot(trc, atom, "permanent_table");
227 }
228 }
229 }
230
231 void
MarkWellKnownSymbols(JSTracer * trc)232 js::MarkWellKnownSymbols(JSTracer* trc)
233 {
234 JSRuntime* rt = trc->runtime();
235
236 if (rt->parentRuntime)
237 return;
238
239 if (WellKnownSymbols* wks = rt->wellKnownSymbols) {
240 for (size_t i = 0; i < JS::WellKnownSymbolLimit; i++)
241 TraceProcessGlobalRoot(trc, wks->get(i).get(), "well_known_symbol");
242 }
243 }
244
245 void
sweepAtoms()246 JSRuntime::sweepAtoms()
247 {
248 if (atoms_)
249 atoms_->sweep();
250 }
251
252 bool
transformToPermanentAtoms(JSContext * cx)253 JSRuntime::transformToPermanentAtoms(JSContext* cx)
254 {
255 MOZ_ASSERT(!parentRuntime);
256
257 // All static strings were created as permanent atoms, now move the contents
258 // of the atoms table into permanentAtoms and mark each as permanent.
259
260 MOZ_ASSERT(!permanentAtoms);
261 permanentAtoms = cx->new_<FrozenAtomSet>(atoms_); // takes ownership of atoms_
262
263 atoms_ = cx->new_<AtomSet>();
264 if (!atoms_ || !atoms_->init(JS_STRING_HASH_COUNT))
265 return false;
266
267 for (FrozenAtomSet::Range r(permanentAtoms->all()); !r.empty(); r.popFront()) {
268 AtomStateEntry entry = r.front();
269 JSAtom* atom = entry.asPtr();
270 atom->morphIntoPermanentAtom();
271 }
272
273 return true;
274 }
275
276 bool
AtomIsPinned(JSContext * cx,JSAtom * atom)277 AtomIsPinned(JSContext* cx, JSAtom* atom)
278 {
279 /* We treat static strings as interned because they're never collected. */
280 if (StaticStrings::isStatic(atom))
281 return true;
282
283 AtomHasher::Lookup lookup(atom);
284
285 /* Likewise, permanent strings are considered to be interned. */
286 MOZ_ASSERT(cx->isPermanentAtomsInitialized());
287 AtomSet::Ptr p = cx->permanentAtoms().readonlyThreadsafeLookup(lookup);
288 if (p)
289 return true;
290
291 AutoLockForExclusiveAccess lock(cx);
292
293 p = cx->runtime()->atoms().lookup(lookup);
294 if (!p)
295 return false;
296
297 return p->isPinned();
298 }
299
300 /* |tbchars| must not point into an inline or short string. */
301 template <typename CharT>
302 MOZ_ALWAYS_INLINE
303 static JSAtom*
AtomizeAndCopyChars(ExclusiveContext * cx,const CharT * tbchars,size_t length,PinningBehavior pin)304 AtomizeAndCopyChars(ExclusiveContext* cx, const CharT* tbchars, size_t length, PinningBehavior pin)
305 {
306 if (JSAtom* s = cx->staticStrings().lookup(tbchars, length))
307 return s;
308
309 AtomHasher::Lookup lookup(tbchars, length);
310
311 // Note: when this function is called while the permanent atoms table is
312 // being initialized (in initializeAtoms()), |permanentAtoms| is not yet
313 // initialized so this lookup is always skipped. Only once
314 // transformToPermanentAtoms() is called does |permanentAtoms| get
315 // initialized and then this lookup will go ahead.
316 if (cx->isPermanentAtomsInitialized()) {
317 AtomSet::Ptr pp = cx->permanentAtoms().readonlyThreadsafeLookup(lookup);
318 if (pp)
319 return pp->asPtr();
320 }
321
322 AutoLockForExclusiveAccess lock(cx);
323
324 AtomSet& atoms = cx->atoms();
325 AtomSet::AddPtr p = atoms.lookupForAdd(lookup);
326 if (p) {
327 JSAtom* atom = p->asPtr();
328 p->setPinned(bool(pin));
329 return atom;
330 }
331
332 AutoCompartment ac(cx, cx->atomsCompartment());
333
334 JSFlatString* flat = NewStringCopyN<NoGC>(cx, tbchars, length);
335 if (!flat) {
336 // Grudgingly forgo last-ditch GC. The alternative would be to release
337 // the lock, manually GC here, and retry from the top. If you fix this,
338 // please also fix or comment the similar case in Symbol::new_.
339 ReportOutOfMemory(cx);
340 return nullptr;
341 }
342
343 JSAtom* atom = flat->morphAtomizedStringIntoAtom(lookup.hash);
344 MOZ_ASSERT(atom->hash() == lookup.hash);
345
346 // We have held the lock since looking up p, and the operations we've done
347 // since then can't GC; therefore the atoms table has not been modified and
348 // p is still valid.
349 if (!atoms.add(p, AtomStateEntry(atom, bool(pin)))) {
350 ReportOutOfMemory(cx); /* SystemAllocPolicy does not report OOM. */
351 return nullptr;
352 }
353
354 return atom;
355 }
356
357 template JSAtom*
358 AtomizeAndCopyChars(ExclusiveContext* cx, const char16_t* tbchars, size_t length, PinningBehavior pin);
359
360 template JSAtom*
361 AtomizeAndCopyChars(ExclusiveContext* cx, const Latin1Char* tbchars, size_t length, PinningBehavior pin);
362
363 JSAtom*
AtomizeString(ExclusiveContext * cx,JSString * str,js::PinningBehavior pin)364 js::AtomizeString(ExclusiveContext* cx, JSString* str,
365 js::PinningBehavior pin /* = js::DoNotPinAtom */)
366 {
367 if (str->isAtom()) {
368 JSAtom& atom = str->asAtom();
369 /* N.B. static atoms are effectively always interned. */
370 if (pin != PinAtom || js::StaticStrings::isStatic(&atom))
371 return &atom;
372
373 AtomHasher::Lookup lookup(&atom);
374
375 /* Likewise, permanent atoms are always interned. */
376 MOZ_ASSERT(cx->isPermanentAtomsInitialized());
377 AtomSet::Ptr p = cx->permanentAtoms().readonlyThreadsafeLookup(lookup);
378 if (p)
379 return &atom;
380
381 AutoLockForExclusiveAccess lock(cx);
382
383 p = cx->atoms().lookup(lookup);
384 MOZ_ASSERT(p); /* Non-static atom must exist in atom state set. */
385 MOZ_ASSERT(p->asPtr() == &atom);
386 MOZ_ASSERT(pin == PinAtom);
387 p->setPinned(bool(pin));
388 return &atom;
389 }
390
391 JSLinearString* linear = str->ensureLinear(cx);
392 if (!linear)
393 return nullptr;
394
395 JS::AutoCheckCannotGC nogc;
396 return linear->hasLatin1Chars()
397 ? AtomizeAndCopyChars(cx, linear->latin1Chars(nogc), linear->length(), pin)
398 : AtomizeAndCopyChars(cx, linear->twoByteChars(nogc), linear->length(), pin);
399 }
400
401 JSAtom*
Atomize(ExclusiveContext * cx,const char * bytes,size_t length,PinningBehavior pin)402 js::Atomize(ExclusiveContext* cx, const char* bytes, size_t length, PinningBehavior pin)
403 {
404 CHECK_REQUEST(cx);
405
406 if (!JSString::validateLength(cx, length))
407 return nullptr;
408
409 const Latin1Char* chars = reinterpret_cast<const Latin1Char*>(bytes);
410 return AtomizeAndCopyChars(cx, chars, length, pin);
411 }
412
413 template <typename CharT>
414 JSAtom*
AtomizeChars(ExclusiveContext * cx,const CharT * chars,size_t length,PinningBehavior pin)415 js::AtomizeChars(ExclusiveContext* cx, const CharT* chars, size_t length, PinningBehavior pin)
416 {
417 CHECK_REQUEST(cx);
418
419 if (!JSString::validateLength(cx, length))
420 return nullptr;
421
422 return AtomizeAndCopyChars(cx, chars, length, pin);
423 }
424
425 template JSAtom*
426 js::AtomizeChars(ExclusiveContext* cx, const Latin1Char* chars, size_t length, PinningBehavior pin);
427
428 template JSAtom*
429 js::AtomizeChars(ExclusiveContext* cx, const char16_t* chars, size_t length, PinningBehavior pin);
430
431 bool
IndexToIdSlow(ExclusiveContext * cx,uint32_t index,MutableHandleId idp)432 js::IndexToIdSlow(ExclusiveContext* cx, uint32_t index, MutableHandleId idp)
433 {
434 MOZ_ASSERT(index > JSID_INT_MAX);
435
436 char16_t buf[UINT32_CHAR_BUFFER_LENGTH];
437 RangedPtr<char16_t> end(ArrayEnd(buf), buf, ArrayEnd(buf));
438 RangedPtr<char16_t> start = BackfillIndexInCharBuffer(index, end);
439
440 JSAtom* atom = AtomizeChars(cx, start.get(), end - start);
441 if (!atom)
442 return false;
443
444 idp.set(JSID_FROM_BITS((size_t)atom));
445 return true;
446 }
447
448 template <AllowGC allowGC>
449 static JSAtom*
ToAtomSlow(ExclusiveContext * cx,typename MaybeRooted<Value,allowGC>::HandleType arg)450 ToAtomSlow(ExclusiveContext* cx, typename MaybeRooted<Value, allowGC>::HandleType arg)
451 {
452 MOZ_ASSERT(!arg.isString());
453
454 Value v = arg;
455 if (!v.isPrimitive()) {
456 if (!cx->shouldBeJSContext() || !allowGC)
457 return nullptr;
458 RootedValue v2(cx, v);
459 if (!ToPrimitive(cx->asJSContext(), JSTYPE_STRING, &v2))
460 return nullptr;
461 v = v2;
462 }
463
464 if (v.isString())
465 return AtomizeString(cx, v.toString());
466 if (v.isInt32())
467 return Int32ToAtom(cx, v.toInt32());
468 if (v.isDouble())
469 return NumberToAtom(cx, v.toDouble());
470 if (v.isBoolean())
471 return v.toBoolean() ? cx->names().true_ : cx->names().false_;
472 if (v.isNull())
473 return cx->names().null;
474 return cx->names().undefined;
475 }
476
477 template <AllowGC allowGC>
478 JSAtom*
ToAtom(ExclusiveContext * cx,typename MaybeRooted<Value,allowGC>::HandleType v)479 js::ToAtom(ExclusiveContext* cx, typename MaybeRooted<Value, allowGC>::HandleType v)
480 {
481 if (!v.isString())
482 return ToAtomSlow<allowGC>(cx, v);
483
484 JSString* str = v.toString();
485 if (str->isAtom())
486 return &str->asAtom();
487
488 JSAtom* atom = AtomizeString(cx, str);
489 if (!atom && !allowGC) {
490 MOZ_ASSERT_IF(cx->isJSContext(), cx->asJSContext()->isThrowingOutOfMemory());
491 cx->recoverFromOutOfMemory();
492 }
493 return atom;
494 }
495
496 template JSAtom*
497 js::ToAtom<CanGC>(ExclusiveContext* cx, HandleValue v);
498
499 template JSAtom*
500 js::ToAtom<NoGC>(ExclusiveContext* cx, Value v);
501
502 template<XDRMode mode>
503 bool
XDRAtom(XDRState<mode> * xdr,MutableHandleAtom atomp)504 js::XDRAtom(XDRState<mode>* xdr, MutableHandleAtom atomp)
505 {
506 if (mode == XDR_ENCODE) {
507 static_assert(JSString::MAX_LENGTH <= INT32_MAX, "String length must fit in 31 bits");
508 uint32_t length = atomp->length();
509 uint32_t lengthAndEncoding = (length << 1) | uint32_t(atomp->hasLatin1Chars());
510 if (!xdr->codeUint32(&lengthAndEncoding))
511 return false;
512
513 JS::AutoCheckCannotGC nogc;
514 return atomp->hasLatin1Chars()
515 ? xdr->codeChars(atomp->latin1Chars(nogc), length)
516 : xdr->codeChars(const_cast<char16_t*>(atomp->twoByteChars(nogc)), length);
517 }
518
519 /* Avoid JSString allocation for already existing atoms. See bug 321985. */
520 uint32_t lengthAndEncoding;
521 if (!xdr->codeUint32(&lengthAndEncoding))
522 return false;
523
524 uint32_t length = lengthAndEncoding >> 1;
525 bool latin1 = lengthAndEncoding & 0x1;
526
527 JSContext* cx = xdr->cx();
528 JSAtom* atom;
529 if (latin1) {
530 const Latin1Char* chars = reinterpret_cast<const Latin1Char*>(xdr->buf.read(length));
531 atom = AtomizeChars(cx, chars, length);
532 } else {
533 #if IS_LITTLE_ENDIAN
534 /* Directly access the little endian chars in the XDR buffer. */
535 const char16_t* chars = reinterpret_cast<const char16_t*>(xdr->buf.read(length * sizeof(char16_t)));
536 atom = AtomizeChars(cx, chars, length);
537 #else
538 /*
539 * We must copy chars to a temporary buffer to convert between little and
540 * big endian data.
541 */
542 char16_t* chars;
543 char16_t stackChars[256];
544 if (length <= ArrayLength(stackChars)) {
545 chars = stackChars;
546 } else {
547 /*
548 * This is very uncommon. Don't use the tempLifoAlloc arena for this as
549 * most allocations here will be bigger than tempLifoAlloc's default
550 * chunk size.
551 */
552 chars = cx->runtime()->pod_malloc<char16_t>(length);
553 if (!chars)
554 return false;
555 }
556
557 JS_ALWAYS_TRUE(xdr->codeChars(chars, length));
558 atom = AtomizeChars(cx, chars, length);
559 if (chars != stackChars)
560 js_free(chars);
561 #endif /* !IS_LITTLE_ENDIAN */
562 }
563
564 if (!atom)
565 return false;
566 atomp.set(atom);
567 return true;
568 }
569
570 template bool
571 js::XDRAtom(XDRState<XDR_ENCODE>* xdr, MutableHandleAtom atomp);
572
573 template bool
574 js::XDRAtom(XDRState<XDR_DECODE>* xdr, MutableHandleAtom atomp);
575
576