1 // Copyright Joyent, Inc. and other Node contributors.
2 //
3 // Permission is hereby granted, free of charge, to any person obtaining a
4 // copy of this software and associated documentation files (the
5 // "Software"), to deal in the Software without restriction, including
6 // without limitation the rights to use, copy, modify, merge, publish,
7 // distribute, sublicense, and/or sell copies of the Software, and to permit
8 // persons to whom the Software is furnished to do so, subject to the
9 // following conditions:
10 //
11 // The above copyright notice and this permission notice shall be included
12 // in all copies or substantial portions of the Software.
13 //
14 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
15 // OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
16 // MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN
17 // NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM,
18 // DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR
19 // OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE
20 // USE OR OTHER DEALINGS IN THE SOFTWARE.
21
22 #ifndef SRC_UTIL_INL_H_
23 #define SRC_UTIL_INL_H_
24
25 #if defined(NODE_WANT_INTERNALS) && NODE_WANT_INTERNALS
26
27 #include <cmath>
28 #include <cstring>
29 #include <locale>
30 #include "util.h"
31
32 // These are defined by <sys/byteorder.h> or <netinet/in.h> on some systems.
33 // To avoid warnings, undefine them before redefining them.
34 #ifdef BSWAP_2
35 # undef BSWAP_2
36 #endif
37 #ifdef BSWAP_4
38 # undef BSWAP_4
39 #endif
40 #ifdef BSWAP_8
41 # undef BSWAP_8
42 #endif
43
44 #if defined(_MSC_VER)
45 #include <intrin.h>
46 #define BSWAP_2(x) _byteswap_ushort(x)
47 #define BSWAP_4(x) _byteswap_ulong(x)
48 #define BSWAP_8(x) _byteswap_uint64(x)
49 #else
50 #define BSWAP_2(x) ((x) << 8) | ((x) >> 8)
51 #define BSWAP_4(x) \
52 (((x) & 0xFF) << 24) | \
53 (((x) & 0xFF00) << 8) | \
54 (((x) >> 8) & 0xFF00) | \
55 (((x) >> 24) & 0xFF)
56 #define BSWAP_8(x) \
57 (((x) & 0xFF00000000000000ull) >> 56) | \
58 (((x) & 0x00FF000000000000ull) >> 40) | \
59 (((x) & 0x0000FF0000000000ull) >> 24) | \
60 (((x) & 0x000000FF00000000ull) >> 8) | \
61 (((x) & 0x00000000FF000000ull) << 8) | \
62 (((x) & 0x0000000000FF0000ull) << 24) | \
63 (((x) & 0x000000000000FF00ull) << 40) | \
64 (((x) & 0x00000000000000FFull) << 56)
65 #endif
66
67 namespace node {
68
69 template <typename T>
ListNode()70 ListNode<T>::ListNode() : prev_(this), next_(this) {}
71
72 template <typename T>
~ListNode()73 ListNode<T>::~ListNode() {
74 Remove();
75 }
76
77 template <typename T>
Remove()78 void ListNode<T>::Remove() {
79 prev_->next_ = next_;
80 next_->prev_ = prev_;
81 prev_ = this;
82 next_ = this;
83 }
84
85 template <typename T>
IsEmpty()86 bool ListNode<T>::IsEmpty() const {
87 return prev_ == this;
88 }
89
90 template <typename T, ListNode<T> (T::*M)>
Iterator(ListNode<T> * node)91 ListHead<T, M>::Iterator::Iterator(ListNode<T>* node) : node_(node) {}
92
93 template <typename T, ListNode<T> (T::*M)>
94 T* ListHead<T, M>::Iterator::operator*() const {
95 return ContainerOf(M, node_);
96 }
97
98 template <typename T, ListNode<T> (T::*M)>
99 const typename ListHead<T, M>::Iterator&
100 ListHead<T, M>::Iterator::operator++() {
101 node_ = node_->next_;
102 return *this;
103 }
104
105 template <typename T, ListNode<T> (T::*M)>
106 bool ListHead<T, M>::Iterator::operator!=(const Iterator& that) const {
107 return node_ != that.node_;
108 }
109
110 template <typename T, ListNode<T> (T::*M)>
~ListHead()111 ListHead<T, M>::~ListHead() {
112 while (IsEmpty() == false)
113 head_.next_->Remove();
114 }
115
116 template <typename T, ListNode<T> (T::*M)>
PushBack(T * element)117 void ListHead<T, M>::PushBack(T* element) {
118 ListNode<T>* that = &(element->*M);
119 head_.prev_->next_ = that;
120 that->prev_ = head_.prev_;
121 that->next_ = &head_;
122 head_.prev_ = that;
123 }
124
125 template <typename T, ListNode<T> (T::*M)>
PushFront(T * element)126 void ListHead<T, M>::PushFront(T* element) {
127 ListNode<T>* that = &(element->*M);
128 head_.next_->prev_ = that;
129 that->prev_ = &head_;
130 that->next_ = head_.next_;
131 head_.next_ = that;
132 }
133
134 template <typename T, ListNode<T> (T::*M)>
IsEmpty()135 bool ListHead<T, M>::IsEmpty() const {
136 return head_.IsEmpty();
137 }
138
139 template <typename T, ListNode<T> (T::*M)>
PopFront()140 T* ListHead<T, M>::PopFront() {
141 if (IsEmpty())
142 return nullptr;
143 ListNode<T>* node = head_.next_;
144 node->Remove();
145 return ContainerOf(M, node);
146 }
147
148 template <typename T, ListNode<T> (T::*M)>
begin()149 typename ListHead<T, M>::Iterator ListHead<T, M>::begin() const {
150 return Iterator(head_.next_);
151 }
152
153 template <typename T, ListNode<T> (T::*M)>
end()154 typename ListHead<T, M>::Iterator ListHead<T, M>::end() const {
155 return Iterator(const_cast<ListNode<T>*>(&head_));
156 }
157
158 template <typename Inner, typename Outer>
OffsetOf(Inner Outer::* field)159 constexpr uintptr_t OffsetOf(Inner Outer::*field) {
160 return reinterpret_cast<uintptr_t>(&(static_cast<Outer*>(nullptr)->*field));
161 }
162
163 template <typename Inner, typename Outer>
ContainerOfHelper(Inner Outer::* field,Inner * pointer)164 ContainerOfHelper<Inner, Outer>::ContainerOfHelper(Inner Outer::*field,
165 Inner* pointer)
166 : pointer_(
167 reinterpret_cast<Outer*>(
168 reinterpret_cast<uintptr_t>(pointer) - OffsetOf(field))) {}
169
170 template <typename Inner, typename Outer>
171 template <typename TypeName>
172 ContainerOfHelper<Inner, Outer>::operator TypeName*() const {
173 return static_cast<TypeName*>(pointer_);
174 }
175
176 template <typename Inner, typename Outer>
ContainerOf(Inner Outer::* field,Inner * pointer)177 constexpr ContainerOfHelper<Inner, Outer> ContainerOf(Inner Outer::*field,
178 Inner* pointer) {
179 return ContainerOfHelper<Inner, Outer>(field, pointer);
180 }
181
OneByteString(v8::Isolate * isolate,const char * data,int length)182 inline v8::Local<v8::String> OneByteString(v8::Isolate* isolate,
183 const char* data,
184 int length) {
185 return v8::String::NewFromOneByte(isolate,
186 reinterpret_cast<const uint8_t*>(data),
187 v8::NewStringType::kNormal,
188 length).ToLocalChecked();
189 }
190
OneByteString(v8::Isolate * isolate,const signed char * data,int length)191 inline v8::Local<v8::String> OneByteString(v8::Isolate* isolate,
192 const signed char* data,
193 int length) {
194 return v8::String::NewFromOneByte(isolate,
195 reinterpret_cast<const uint8_t*>(data),
196 v8::NewStringType::kNormal,
197 length).ToLocalChecked();
198 }
199
OneByteString(v8::Isolate * isolate,const unsigned char * data,int length)200 inline v8::Local<v8::String> OneByteString(v8::Isolate* isolate,
201 const unsigned char* data,
202 int length) {
203 return v8::String::NewFromOneByte(
204 isolate, data, v8::NewStringType::kNormal, length)
205 .ToLocalChecked();
206 }
207
SwapBytes16(char * data,size_t nbytes)208 void SwapBytes16(char* data, size_t nbytes) {
209 CHECK_EQ(nbytes % 2, 0);
210
211 #if defined(_MSC_VER)
212 if (AlignUp(data, sizeof(uint16_t)) == data) {
213 // MSVC has no strict aliasing, and is able to highly optimize this case.
214 uint16_t* data16 = reinterpret_cast<uint16_t*>(data);
215 size_t len16 = nbytes / sizeof(*data16);
216 for (size_t i = 0; i < len16; i++) {
217 data16[i] = BSWAP_2(data16[i]);
218 }
219 return;
220 }
221 #endif
222
223 uint16_t temp;
224 for (size_t i = 0; i < nbytes; i += sizeof(temp)) {
225 memcpy(&temp, &data[i], sizeof(temp));
226 temp = BSWAP_2(temp);
227 memcpy(&data[i], &temp, sizeof(temp));
228 }
229 }
230
SwapBytes32(char * data,size_t nbytes)231 void SwapBytes32(char* data, size_t nbytes) {
232 CHECK_EQ(nbytes % 4, 0);
233
234 #if defined(_MSC_VER)
235 // MSVC has no strict aliasing, and is able to highly optimize this case.
236 if (AlignUp(data, sizeof(uint32_t)) == data) {
237 uint32_t* data32 = reinterpret_cast<uint32_t*>(data);
238 size_t len32 = nbytes / sizeof(*data32);
239 for (size_t i = 0; i < len32; i++) {
240 data32[i] = BSWAP_4(data32[i]);
241 }
242 return;
243 }
244 #endif
245
246 uint32_t temp;
247 for (size_t i = 0; i < nbytes; i += sizeof(temp)) {
248 memcpy(&temp, &data[i], sizeof(temp));
249 temp = BSWAP_4(temp);
250 memcpy(&data[i], &temp, sizeof(temp));
251 }
252 }
253
SwapBytes64(char * data,size_t nbytes)254 void SwapBytes64(char* data, size_t nbytes) {
255 CHECK_EQ(nbytes % 8, 0);
256
257 #if defined(_MSC_VER)
258 if (AlignUp(data, sizeof(uint64_t)) == data) {
259 // MSVC has no strict aliasing, and is able to highly optimize this case.
260 uint64_t* data64 = reinterpret_cast<uint64_t*>(data);
261 size_t len64 = nbytes / sizeof(*data64);
262 for (size_t i = 0; i < len64; i++) {
263 data64[i] = BSWAP_8(data64[i]);
264 }
265 return;
266 }
267 #endif
268
269 uint64_t temp;
270 for (size_t i = 0; i < nbytes; i += sizeof(temp)) {
271 memcpy(&temp, &data[i], sizeof(temp));
272 temp = BSWAP_8(temp);
273 memcpy(&data[i], &temp, sizeof(temp));
274 }
275 }
276
ToLower(char c)277 char ToLower(char c) {
278 return std::tolower(c, std::locale::classic());
279 }
280
ToLower(const std::string & in)281 std::string ToLower(const std::string& in) {
282 std::string out(in.size(), 0);
283 for (size_t i = 0; i < in.size(); ++i)
284 out[i] = ToLower(in[i]);
285 return out;
286 }
287
ToUpper(char c)288 char ToUpper(char c) {
289 return std::toupper(c, std::locale::classic());
290 }
291
ToUpper(const std::string & in)292 std::string ToUpper(const std::string& in) {
293 std::string out(in.size(), 0);
294 for (size_t i = 0; i < in.size(); ++i)
295 out[i] = ToUpper(in[i]);
296 return out;
297 }
298
StringEqualNoCase(const char * a,const char * b)299 bool StringEqualNoCase(const char* a, const char* b) {
300 while (ToLower(*a) == ToLower(*b++)) {
301 if (*a++ == '\0')
302 return true;
303 }
304 return false;
305 }
306
StringEqualNoCaseN(const char * a,const char * b,size_t length)307 bool StringEqualNoCaseN(const char* a, const char* b, size_t length) {
308 for (size_t i = 0; i < length; i++) {
309 if (ToLower(a[i]) != ToLower(b[i]))
310 return false;
311 if (a[i] == '\0')
312 return true;
313 }
314 return true;
315 }
316
317 template <typename T>
MultiplyWithOverflowCheck(T a,T b)318 inline T MultiplyWithOverflowCheck(T a, T b) {
319 auto ret = a * b;
320 if (a != 0)
321 CHECK_EQ(b, ret / a);
322
323 return ret;
324 }
325
326 // These should be used in our code as opposed to the native
327 // versions as they abstract out some platform and or
328 // compiler version specific functionality.
329 // malloc(0) and realloc(ptr, 0) have implementation-defined behavior in
330 // that the standard allows them to either return a unique pointer or a
331 // nullptr for zero-sized allocation requests. Normalize by always using
332 // a nullptr.
333 template <typename T>
UncheckedRealloc(T * pointer,size_t n)334 T* UncheckedRealloc(T* pointer, size_t n) {
335 size_t full_size = MultiplyWithOverflowCheck(sizeof(T), n);
336
337 if (full_size == 0) {
338 free(pointer);
339 return nullptr;
340 }
341
342 void* allocated = realloc(pointer, full_size);
343
344 if (UNLIKELY(allocated == nullptr)) {
345 // Tell V8 that memory is low and retry.
346 LowMemoryNotification();
347 allocated = realloc(pointer, full_size);
348 }
349
350 return static_cast<T*>(allocated);
351 }
352
353 // As per spec realloc behaves like malloc if passed nullptr.
354 template <typename T>
UncheckedMalloc(size_t n)355 inline T* UncheckedMalloc(size_t n) {
356 if (n == 0) n = 1;
357 return UncheckedRealloc<T>(nullptr, n);
358 }
359
360 template <typename T>
UncheckedCalloc(size_t n)361 inline T* UncheckedCalloc(size_t n) {
362 if (n == 0) n = 1;
363 MultiplyWithOverflowCheck(sizeof(T), n);
364 return static_cast<T*>(calloc(n, sizeof(T)));
365 }
366
367 template <typename T>
Realloc(T * pointer,size_t n)368 inline T* Realloc(T* pointer, size_t n) {
369 T* ret = UncheckedRealloc(pointer, n);
370 CHECK_IMPLIES(n > 0, ret != nullptr);
371 return ret;
372 }
373
374 template <typename T>
Malloc(size_t n)375 inline T* Malloc(size_t n) {
376 T* ret = UncheckedMalloc<T>(n);
377 CHECK_IMPLIES(n > 0, ret != nullptr);
378 return ret;
379 }
380
381 template <typename T>
Calloc(size_t n)382 inline T* Calloc(size_t n) {
383 T* ret = UncheckedCalloc<T>(n);
384 CHECK_IMPLIES(n > 0, ret != nullptr);
385 return ret;
386 }
387
388 // Shortcuts for char*.
Malloc(size_t n)389 inline char* Malloc(size_t n) { return Malloc<char>(n); }
Calloc(size_t n)390 inline char* Calloc(size_t n) { return Calloc<char>(n); }
UncheckedMalloc(size_t n)391 inline char* UncheckedMalloc(size_t n) { return UncheckedMalloc<char>(n); }
UncheckedCalloc(size_t n)392 inline char* UncheckedCalloc(size_t n) { return UncheckedCalloc<char>(n); }
393
394 // This is a helper in the .cc file so including util-inl.h doesn't include more
395 // headers than we really need to.
396 void ThrowErrStringTooLong(v8::Isolate* isolate);
397
ToV8Value(v8::Local<v8::Context> context,const std::string & str,v8::Isolate * isolate)398 v8::MaybeLocal<v8::Value> ToV8Value(v8::Local<v8::Context> context,
399 const std::string& str,
400 v8::Isolate* isolate) {
401 if (isolate == nullptr) isolate = context->GetIsolate();
402 if (UNLIKELY(str.size() >= static_cast<size_t>(v8::String::kMaxLength))) {
403 // V8 only has a TODO comment about adding an exception when the maximum
404 // string size is exceeded.
405 ThrowErrStringTooLong(isolate);
406 return v8::MaybeLocal<v8::Value>();
407 }
408
409 return v8::String::NewFromUtf8(
410 isolate, str.data(), v8::NewStringType::kNormal, str.size())
411 .FromMaybe(v8::Local<v8::String>());
412 }
413
414 template <typename T>
ToV8Value(v8::Local<v8::Context> context,const std::vector<T> & vec,v8::Isolate * isolate)415 v8::MaybeLocal<v8::Value> ToV8Value(v8::Local<v8::Context> context,
416 const std::vector<T>& vec,
417 v8::Isolate* isolate) {
418 if (isolate == nullptr) isolate = context->GetIsolate();
419 v8::EscapableHandleScope handle_scope(isolate);
420
421 MaybeStackBuffer<v8::Local<v8::Value>, 128> arr(vec.size());
422 arr.SetLength(vec.size());
423 for (size_t i = 0; i < vec.size(); ++i) {
424 if (!ToV8Value(context, vec[i], isolate).ToLocal(&arr[i]))
425 return v8::MaybeLocal<v8::Value>();
426 }
427
428 return handle_scope.Escape(v8::Array::New(isolate, arr.out(), arr.length()));
429 }
430
431 template <typename T, typename U>
ToV8Value(v8::Local<v8::Context> context,const std::unordered_map<T,U> & map,v8::Isolate * isolate)432 v8::MaybeLocal<v8::Value> ToV8Value(v8::Local<v8::Context> context,
433 const std::unordered_map<T, U>& map,
434 v8::Isolate* isolate) {
435 if (isolate == nullptr) isolate = context->GetIsolate();
436 v8::EscapableHandleScope handle_scope(isolate);
437
438 v8::Local<v8::Map> ret = v8::Map::New(isolate);
439 for (const auto& item : map) {
440 v8::Local<v8::Value> first, second;
441 if (!ToV8Value(context, item.first, isolate).ToLocal(&first) ||
442 !ToV8Value(context, item.second, isolate).ToLocal(&second) ||
443 ret->Set(context, first, second).IsEmpty()) {
444 return v8::MaybeLocal<v8::Value>();
445 }
446 }
447
448 return handle_scope.Escape(ret);
449 }
450
451 template <typename T, typename >
ToV8Value(v8::Local<v8::Context> context,const T & number,v8::Isolate * isolate)452 v8::MaybeLocal<v8::Value> ToV8Value(v8::Local<v8::Context> context,
453 const T& number,
454 v8::Isolate* isolate) {
455 if (isolate == nullptr) isolate = context->GetIsolate();
456
457 using Limits = std::numeric_limits<T>;
458 // Choose Uint32, Int32, or Double depending on range checks.
459 // These checks should all collapse at compile time.
460 if (static_cast<uint32_t>(Limits::max()) <=
461 std::numeric_limits<uint32_t>::max() &&
462 static_cast<uint32_t>(Limits::min()) >=
463 std::numeric_limits<uint32_t>::min() && Limits::is_exact) {
464 return v8::Integer::NewFromUnsigned(isolate, static_cast<uint32_t>(number));
465 }
466
467 if (static_cast<int32_t>(Limits::max()) <=
468 std::numeric_limits<int32_t>::max() &&
469 static_cast<int32_t>(Limits::min()) >=
470 std::numeric_limits<int32_t>::min() && Limits::is_exact) {
471 return v8::Integer::New(isolate, static_cast<int32_t>(number));
472 }
473
474 return v8::Number::New(isolate, static_cast<double>(number));
475 }
476
SlicedArguments(const v8::FunctionCallbackInfo<v8::Value> & args,size_t start)477 SlicedArguments::SlicedArguments(
478 const v8::FunctionCallbackInfo<v8::Value>& args, size_t start) {
479 const size_t length = static_cast<size_t>(args.Length());
480 if (start >= length) return;
481 const size_t size = length - start;
482
483 AllocateSufficientStorage(size);
484 for (size_t i = 0; i < size; ++i)
485 (*this)[i] = args[i + start];
486 }
487
488 template <typename T, size_t S>
ArrayBufferViewContents(v8::Local<v8::Value> value)489 ArrayBufferViewContents<T, S>::ArrayBufferViewContents(
490 v8::Local<v8::Value> value) {
491 CHECK(value->IsArrayBufferView());
492 Read(value.As<v8::ArrayBufferView>());
493 }
494
495 template <typename T, size_t S>
ArrayBufferViewContents(v8::Local<v8::Object> value)496 ArrayBufferViewContents<T, S>::ArrayBufferViewContents(
497 v8::Local<v8::Object> value) {
498 CHECK(value->IsArrayBufferView());
499 Read(value.As<v8::ArrayBufferView>());
500 }
501
502 template <typename T, size_t S>
ArrayBufferViewContents(v8::Local<v8::ArrayBufferView> abv)503 ArrayBufferViewContents<T, S>::ArrayBufferViewContents(
504 v8::Local<v8::ArrayBufferView> abv) {
505 Read(abv);
506 }
507
508 template <typename T, size_t S>
Read(v8::Local<v8::ArrayBufferView> abv)509 void ArrayBufferViewContents<T, S>::Read(v8::Local<v8::ArrayBufferView> abv) {
510 static_assert(sizeof(T) == 1, "Only supports one-byte data at the moment");
511 length_ = abv->ByteLength();
512 if (length_ > sizeof(stack_storage_) || abv->HasBuffer()) {
513 data_ = static_cast<T*>(abv->Buffer()->GetBackingStore()->Data()) +
514 abv->ByteOffset();
515 } else {
516 abv->CopyContents(stack_storage_, sizeof(stack_storage_));
517 data_ = stack_storage_;
518 }
519 }
520
521 // ECMA262 20.1.2.5
IsSafeJsInt(v8::Local<v8::Value> v)522 inline bool IsSafeJsInt(v8::Local<v8::Value> v) {
523 if (!v->IsNumber()) return false;
524 double v_d = v.As<v8::Number>()->Value();
525 if (std::isnan(v_d)) return false;
526 if (std::isinf(v_d)) return false;
527 if (std::trunc(v_d) != v_d) return false; // not int
528 if (std::abs(v_d) <= static_cast<double>(kMaxSafeJsInteger)) return true;
529 return false;
530 }
531
HashImpl(const char * str)532 constexpr size_t FastStringKey::HashImpl(const char* str) {
533 // Low-quality hash (djb2), but just fine for current use cases.
534 size_t h = 5381;
535 while (*str != '\0') {
536 h = h * 33 + *(str++); // NOLINT(readability/pointer_notation)
537 }
538 return h;
539 }
540
operator()541 constexpr size_t FastStringKey::Hash::operator()(
542 const FastStringKey& key) const {
543 return key.cached_hash_;
544 }
545
546 constexpr bool FastStringKey::operator==(const FastStringKey& other) const {
547 const char* p1 = name_;
548 const char* p2 = other.name_;
549 if (p1 == p2) return true;
550 do {
551 if (*(p1++) != *(p2++)) return false;
552 } while (*p1 != '\0');
553 return *p2 == '\0';
554 }
555
FastStringKey(const char * name)556 constexpr FastStringKey::FastStringKey(const char* name)
557 : name_(name), cached_hash_(HashImpl(name)) {}
558
c_str()559 constexpr const char* FastStringKey::c_str() const {
560 return name_;
561 }
562
563 } // namespace node
564
565 #endif // defined(NODE_WANT_INTERNALS) && NODE_WANT_INTERNALS
566
567 #endif // SRC_UTIL_INL_H_
568