1/* 2 * Copyright (c) 2009-2013 Apple Inc. All rights reserved. 3 * 4 * @APPLE_APACHE_LICENSE_HEADER_START@ 5 * 6 * Licensed under the Apache License, Version 2.0 (the "License"); 7 * you may not use this file except in compliance with the License. 8 * You may obtain a copy of the License at 9 * 10 * http://www.apache.org/licenses/LICENSE-2.0 11 * 12 * Unless required by applicable law or agreed to in writing, software 13 * distributed under the License is distributed on an "AS IS" BASIS, 14 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 15 * See the License for the specific language governing permissions and 16 * limitations under the License. 17 * 18 * @APPLE_APACHE_LICENSE_HEADER_END@ 19 */ 20 21#include "internal.h" 22 23// Dispatch data objects are dispatch objects with standard retain/release 24// memory management. A dispatch data object either points to a number of other 25// dispatch data objects or is a leaf data object. A leaf data object contains 26// a pointer to represented memory. A composite data object specifies the total 27// size of data it represents and list of constituent records. 28// 29// A leaf data object always points to a full represented buffer, a composite 30// dispatch data object is needed to represent a subrange of a memory region. 31 32#if USE_OBJC 33#define _dispatch_data_retain(x) _dispatch_objc_retain(x) 34#define _dispatch_data_release(x) _dispatch_objc_release(x) 35#else 36#define _dispatch_data_retain(x) dispatch_retain(x) 37#define _dispatch_data_release(x) dispatch_release(x) 38#endif 39 40const dispatch_block_t _dispatch_data_destructor_free = ^{ 41 DISPATCH_CRASH("free destructor called"); 42}; 43 44const dispatch_block_t _dispatch_data_destructor_none = ^{ 45 DISPATCH_CRASH("none destructor called"); 46}; 47 48const dispatch_block_t _dispatch_data_destructor_vm_deallocate = ^{ 49 DISPATCH_CRASH("vmdeallocate destructor called"); 50}; 51 52const dispatch_block_t _dispatch_data_destructor_inline = ^{ 53 DISPATCH_CRASH("inline destructor called"); 54}; 55 56struct dispatch_data_s _dispatch_data_empty = { 57 .do_vtable = DISPATCH_DATA_EMPTY_CLASS, 58#if !USE_OBJC 59 .do_ref_cnt = DISPATCH_OBJECT_GLOBAL_REFCNT, 60 .do_xref_cnt = DISPATCH_OBJECT_GLOBAL_REFCNT, 61 .do_next = DISPATCH_OBJECT_LISTLESS, 62#endif 63}; 64 65DISPATCH_ALWAYS_INLINE 66static inline dispatch_data_t 67_dispatch_data_alloc(size_t n, size_t extra) 68{ 69 dispatch_data_t data = _dispatch_alloc(DISPATCH_DATA_CLASS, 70 sizeof(struct dispatch_data_s) + extra + 71 (n ? n * sizeof(range_record) - sizeof(data->buf) : 0)); 72 data->num_records = n; 73#if !USE_OBJC 74 data->do_targetq = dispatch_get_global_queue( 75 DISPATCH_QUEUE_PRIORITY_DEFAULT, 0); 76 data->do_next = DISPATCH_OBJECT_LISTLESS; 77#endif 78 return data; 79} 80 81static void 82_dispatch_data_destroy_buffer(const void* buffer, size_t size, 83 dispatch_queue_t queue, dispatch_block_t destructor) 84{ 85 if (destructor == DISPATCH_DATA_DESTRUCTOR_FREE) { 86 free((void*)buffer); 87 } else if (destructor == DISPATCH_DATA_DESTRUCTOR_NONE) { 88 // do nothing 89 } else if (destructor == DISPATCH_DATA_DESTRUCTOR_VM_DEALLOCATE) { 90 mach_vm_size_t vm_size = size; 91 mach_vm_address_t vm_addr = (uintptr_t)buffer; 92 mach_vm_deallocate(mach_task_self(), vm_addr, vm_size); 93 } else { 94 if (!queue) { 95 queue = dispatch_get_global_queue( 96 DISPATCH_QUEUE_PRIORITY_DEFAULT, 0); 97 } 98 dispatch_async_f(queue, destructor, _dispatch_call_block_and_release); 99 } 100} 101 102DISPATCH_ALWAYS_INLINE 103static inline void 104_dispatch_data_init(dispatch_data_t data, const void *buffer, size_t size, 105 dispatch_queue_t queue, dispatch_block_t destructor) 106{ 107 data->buf = buffer; 108 data->size = size; 109 data->destructor = destructor; 110#if DISPATCH_DATA_USE_LEAF_MEMBER 111 data->leaf = true; 112 data->num_records = 1; 113#endif 114 if (queue) { 115 _dispatch_retain(queue); 116 data->do_targetq = queue; 117 } 118} 119 120void 121dispatch_data_init(dispatch_data_t data, const void *buffer, size_t size, 122 dispatch_block_t destructor) 123{ 124 if (!buffer || !size) { 125 if (destructor) { 126 _dispatch_data_destroy_buffer(buffer, size, NULL, 127 _dispatch_Block_copy(destructor)); 128 } 129 buffer = NULL; 130 size = 0; 131 destructor = DISPATCH_DATA_DESTRUCTOR_NONE; 132 } 133 _dispatch_data_init(data, buffer, size, NULL, destructor); 134} 135 136dispatch_data_t 137dispatch_data_create(const void* buffer, size_t size, dispatch_queue_t queue, 138 dispatch_block_t destructor) 139{ 140 dispatch_data_t data; 141 void *data_buf = NULL; 142 if (!buffer || !size) { 143 // Empty data requested so return the singleton empty object. Call 144 // destructor immediately in this case to ensure any unused associated 145 // storage is released. 146 if (destructor) { 147 _dispatch_data_destroy_buffer(buffer, size, queue, 148 _dispatch_Block_copy(destructor)); 149 } 150 return dispatch_data_empty; 151 } 152 if (destructor == DISPATCH_DATA_DESTRUCTOR_DEFAULT) { 153 // The default destructor was provided, indicating the data should be 154 // copied. 155 data_buf = malloc(size); 156 if (slowpath(!data_buf)) { 157 return NULL; 158 } 159 buffer = memcpy(data_buf, buffer, size); 160 data = _dispatch_data_alloc(0, 0); 161 destructor = DISPATCH_DATA_DESTRUCTOR_FREE; 162 } else if (destructor == DISPATCH_DATA_DESTRUCTOR_INLINE) { 163 data = _dispatch_data_alloc(0, size); 164 buffer = memcpy((void*)data + sizeof(struct dispatch_data_s), buffer, 165 size); 166 destructor = DISPATCH_DATA_DESTRUCTOR_NONE; 167 } else { 168 data = _dispatch_data_alloc(0, 0); 169 destructor = _dispatch_Block_copy(destructor); 170 } 171 _dispatch_data_init(data, buffer, size, queue, destructor); 172 return data; 173} 174 175dispatch_data_t 176dispatch_data_create_f(const void *buffer, size_t size, dispatch_queue_t queue, 177 dispatch_function_t destructor_function) 178{ 179 dispatch_block_t destructor = (dispatch_block_t)destructor_function; 180 if (destructor != DISPATCH_DATA_DESTRUCTOR_DEFAULT && 181 destructor != DISPATCH_DATA_DESTRUCTOR_FREE && 182 destructor != DISPATCH_DATA_DESTRUCTOR_NONE && 183 destructor != DISPATCH_DATA_DESTRUCTOR_VM_DEALLOCATE && 184 destructor != DISPATCH_DATA_DESTRUCTOR_INLINE) { 185 destructor = ^{ destructor_function((void*)buffer); }; 186 } 187 return dispatch_data_create(buffer, size, queue, destructor); 188} 189 190dispatch_data_t 191dispatch_data_create_alloc(size_t size, void** buffer_ptr) 192{ 193 dispatch_data_t data = dispatch_data_empty; 194 void *buffer = NULL; 195 196 if (slowpath(!size)) { 197 goto out; 198 } 199 data = _dispatch_data_alloc(0, size); 200 buffer = (void*)data + sizeof(struct dispatch_data_s); 201 _dispatch_data_init(data, buffer, size, NULL, 202 DISPATCH_DATA_DESTRUCTOR_NONE); 203out: 204 if (buffer_ptr) { 205 *buffer_ptr = buffer; 206 } 207 return data; 208} 209 210void 211_dispatch_data_dispose(dispatch_data_t dd) 212{ 213 dispatch_block_t destructor = dd->destructor; 214 if (destructor == NULL) { 215 size_t i; 216 for (i = 0; i < _dispatch_data_num_records(dd); ++i) { 217 _dispatch_data_release(dd->records[i].data_object); 218 } 219 } else { 220 _dispatch_data_destroy_buffer(dd->buf, dd->size, dd->do_targetq, 221 destructor); 222 } 223} 224 225size_t 226_dispatch_data_debug(dispatch_data_t dd, char* buf, size_t bufsiz) 227{ 228 size_t offset = 0; 229 offset += dsnprintf(&buf[offset], bufsiz - offset, "data[%p] = { ", dd); 230 if (_dispatch_data_leaf(dd)) { 231 offset += dsnprintf(&buf[offset], bufsiz - offset, 232 "leaf, size = %zd, buf = %p ", dd->size, dd->buf); 233 } else { 234 offset += dsnprintf(&buf[offset], bufsiz - offset, 235 "composite, size = %zd, num_records = %zd ", dd->size, 236 _dispatch_data_num_records(dd)); 237 size_t i; 238 for (i = 0; i < _dispatch_data_num_records(dd); ++i) { 239 range_record r = dd->records[i]; 240 offset += dsnprintf(&buf[offset], bufsiz - offset, "record[%zd] = " 241 "{ from = %zd, length = %zd, data_object = %p }, ", i, 242 r.from, r.length, r.data_object); 243 } 244 } 245 offset += dsnprintf(&buf[offset], bufsiz - offset, "}"); 246 return offset; 247} 248 249size_t 250dispatch_data_get_size(dispatch_data_t dd) 251{ 252 return dd->size; 253} 254 255dispatch_data_t 256dispatch_data_create_concat(dispatch_data_t dd1, dispatch_data_t dd2) 257{ 258 dispatch_data_t data; 259 if (!dd1->size) { 260 _dispatch_data_retain(dd2); 261 return dd2; 262 } 263 if (!dd2->size) { 264 _dispatch_data_retain(dd1); 265 return dd1; 266 } 267 data = _dispatch_data_alloc(_dispatch_data_num_records(dd1) + 268 _dispatch_data_num_records(dd2), 0); 269 data->size = dd1->size + dd2->size; 270 // Copy the constituent records into the newly created data object 271 // Reference leaf objects as sub-objects 272 if (_dispatch_data_leaf(dd1)) { 273 data->records[0].from = 0; 274 data->records[0].length = dd1->size; 275 data->records[0].data_object = dd1; 276 } else { 277 memcpy(data->records, dd1->records, _dispatch_data_num_records(dd1) * 278 sizeof(range_record)); 279 } 280 if (_dispatch_data_leaf(dd2)) { 281 data->records[_dispatch_data_num_records(dd1)].from = 0; 282 data->records[_dispatch_data_num_records(dd1)].length = dd2->size; 283 data->records[_dispatch_data_num_records(dd1)].data_object = dd2; 284 } else { 285 memcpy(data->records + _dispatch_data_num_records(dd1), dd2->records, 286 _dispatch_data_num_records(dd2) * sizeof(range_record)); 287 } 288 size_t i; 289 for (i = 0; i < _dispatch_data_num_records(data); ++i) { 290 _dispatch_data_retain(data->records[i].data_object); 291 } 292 return data; 293} 294 295dispatch_data_t 296dispatch_data_create_subrange(dispatch_data_t dd, size_t offset, 297 size_t length) 298{ 299 dispatch_data_t data; 300 if (offset >= dd->size || !length) { 301 return dispatch_data_empty; 302 } else if ((offset + length) > dd->size) { 303 length = dd->size - offset; 304 } else if (length == dd->size) { 305 _dispatch_data_retain(dd); 306 return dd; 307 } 308 if (_dispatch_data_leaf(dd)) { 309 data = _dispatch_data_alloc(1, 0); 310 data->size = length; 311 data->records[0].from = offset; 312 data->records[0].length = length; 313 data->records[0].data_object = dd; 314 _dispatch_data_retain(dd); 315 return data; 316 } 317 // Subrange of a composite dispatch data object: find the record containing 318 // the specified offset 319 data = dispatch_data_empty; 320 size_t i = 0, bytes_left = length; 321 while (i < _dispatch_data_num_records(dd) && 322 offset >= dd->records[i].length) { 323 offset -= dd->records[i++].length; 324 } 325 while (i < _dispatch_data_num_records(dd)) { 326 size_t record_len = dd->records[i].length - offset; 327 if (record_len > bytes_left) { 328 record_len = bytes_left; 329 } 330 dispatch_data_t subrange = dispatch_data_create_subrange( 331 dd->records[i].data_object, dd->records[i].from + offset, 332 record_len); 333 dispatch_data_t concat = dispatch_data_create_concat(data, subrange); 334 _dispatch_data_release(data); 335 _dispatch_data_release(subrange); 336 data = concat; 337 bytes_left -= record_len; 338 if (!bytes_left) { 339 return data; 340 } 341 offset = 0; 342 i++; 343 } 344 // Crashing here indicates memory corruption of passed in data object 345 DISPATCH_CRASH("dispatch_data_create_subrange out of bounds"); 346 return NULL; 347} 348 349// When mapping a leaf object or a subrange of a leaf object, return a direct 350// pointer to the represented buffer. For all other data objects, copy the 351// represented buffers into a contiguous area. In the future it might 352// be possible to relocate the buffers instead (if not marked as locked). 353dispatch_data_t 354dispatch_data_create_map(dispatch_data_t dd, const void **buffer_ptr, 355 size_t *size_ptr) 356{ 357 dispatch_data_t data = dd; 358 const void *buffer = NULL; 359 size_t size = dd->size, offset = 0; 360 if (!size) { 361 data = dispatch_data_empty; 362 goto out; 363 } 364 if (!_dispatch_data_leaf(dd) && _dispatch_data_num_records(dd) == 1 && 365 _dispatch_data_leaf(dd->records[0].data_object)) { 366 offset = dd->records[0].from; 367 dd = dd->records[0].data_object; 368 } 369 if (_dispatch_data_leaf(dd)) { 370 _dispatch_data_retain(data); 371 buffer = dd->buf + offset; 372 goto out; 373 } 374 // Composite data object, copy the represented buffers 375 buffer = malloc(size); 376 if (!buffer) { 377 data = NULL; 378 size = 0; 379 goto out; 380 } 381 dispatch_data_apply(dd, ^(dispatch_data_t region DISPATCH_UNUSED, 382 size_t off, const void* buf, size_t len) { 383 memcpy((void*)buffer + off, buf, len); 384 return (bool)true; 385 }); 386 data = dispatch_data_create(buffer, size, NULL, 387 DISPATCH_DATA_DESTRUCTOR_FREE); 388out: 389 if (buffer_ptr) { 390 *buffer_ptr = buffer; 391 } 392 if (size_ptr) { 393 *size_ptr = size; 394 } 395 return data; 396} 397 398static bool 399_dispatch_data_apply(dispatch_data_t dd, size_t offset, size_t from, 400 size_t size, void *ctxt, dispatch_data_applier_function_t applier) 401{ 402 bool result = true; 403 dispatch_data_t data = dd; 404 const void *buffer; 405 dispatch_assert(dd->size); 406 if (!_dispatch_data_leaf(dd) && _dispatch_data_num_records(dd) == 1 && 407 _dispatch_data_leaf(dd->records[0].data_object)) { 408 from = dd->records[0].from; 409 dd = dd->records[0].data_object; 410 } 411 if (_dispatch_data_leaf(dd)) { 412 buffer = dd->buf + from; 413 return _dispatch_client_callout3(ctxt, data, offset, buffer, size, 414 applier); 415 } 416 size_t i; 417 for (i = 0; i < _dispatch_data_num_records(dd) && result; ++i) { 418 result = _dispatch_data_apply(dd->records[i].data_object, 419 offset, dd->records[i].from, dd->records[i].length, ctxt, 420 applier); 421 offset += dd->records[i].length; 422 } 423 return result; 424} 425 426bool 427dispatch_data_apply_f(dispatch_data_t dd, void *ctxt, 428 dispatch_data_applier_function_t applier) 429{ 430 if (!dd->size) { 431 return true; 432 } 433 return _dispatch_data_apply(dd, 0, 0, dd->size, ctxt, applier); 434} 435 436bool 437dispatch_data_apply(dispatch_data_t dd, dispatch_data_applier_t applier) 438{ 439 if (!dd->size) { 440 return true; 441 } 442 return _dispatch_data_apply(dd, 0, 0, dd->size, applier, 443 (dispatch_data_applier_function_t)_dispatch_Block_invoke(applier)); 444} 445 446// Returs either a leaf object or an object composed of a single leaf object 447dispatch_data_t 448dispatch_data_copy_region(dispatch_data_t dd, size_t location, 449 size_t *offset_ptr) 450{ 451 if (location >= dd->size) { 452 *offset_ptr = 0; 453 return dispatch_data_empty; 454 } 455 dispatch_data_t data; 456 size_t size = dd->size, offset = 0, from = 0; 457 while (true) { 458 if (_dispatch_data_leaf(dd)) { 459 _dispatch_data_retain(dd); 460 *offset_ptr = offset; 461 if (size == dd->size) { 462 return dd; 463 } else { 464 // Create a new object for the requested subrange of the leaf 465 data = _dispatch_data_alloc(1, 0); 466 data->size = size; 467 data->records[0].from = from; 468 data->records[0].length = size; 469 data->records[0].data_object = dd; 470 return data; 471 } 472 } else { 473 // Find record at the specified location 474 size_t i, pos; 475 for (i = 0; i < _dispatch_data_num_records(dd); ++i) { 476 pos = offset + dd->records[i].length; 477 if (location < pos) { 478 size = dd->records[i].length; 479 from = dd->records[i].from; 480 data = dd->records[i].data_object; 481 if (_dispatch_data_num_records(dd) == 1 && 482 _dispatch_data_leaf(data)) { 483 // Return objects composed of a single leaf node 484 *offset_ptr = offset; 485 _dispatch_data_retain(dd); 486 return dd; 487 } else { 488 // Drill down into other objects 489 dd = data; 490 break; 491 } 492 } else { 493 offset = pos; 494 } 495 } 496 } 497 } 498} 499 500#if HAVE_MACH 501 502#ifndef MAP_MEM_VM_COPY 503#define MAP_MEM_VM_COPY 0x200000 // <rdar://problem/13336613> 504#endif 505 506mach_port_t 507dispatch_data_make_memory_entry(dispatch_data_t dd) 508{ 509 mach_port_t mep = MACH_PORT_NULL; 510 memory_object_size_t mos; 511 mach_vm_size_t vm_size = dd->size; 512 mach_vm_address_t vm_addr; 513 vm_prot_t flags; 514 kern_return_t kr; 515 bool copy = (dd->destructor != DISPATCH_DATA_DESTRUCTOR_VM_DEALLOCATE); 516 517retry: 518 if (copy) { 519 vm_addr = vm_page_size; 520 kr = mach_vm_allocate(mach_task_self(), &vm_addr, vm_size, 521 VM_FLAGS_ANYWHERE); 522 if (kr) { 523 if (kr != KERN_NO_SPACE) { 524 (void)dispatch_assume_zero(kr); 525 } 526 return mep; 527 } 528 dispatch_data_apply(dd, ^(dispatch_data_t region DISPATCH_UNUSED, 529 size_t off, const void* buf, size_t len) { 530 memcpy((void*)(vm_addr + off), buf, len); 531 return (bool)true; 532 }); 533 } else { 534 vm_addr = (uintptr_t)dd->buf; 535 } 536 flags = VM_PROT_DEFAULT|VM_PROT_IS_MASK|MAP_MEM_VM_COPY; 537 mos = vm_size; 538 kr = mach_make_memory_entry_64(mach_task_self(), &mos, vm_addr, flags, 539 &mep, MACH_PORT_NULL); 540 if (kr == KERN_INVALID_VALUE) { 541 // Fallback in case MAP_MEM_VM_COPY is not supported 542 flags &= ~MAP_MEM_VM_COPY; 543 kr = mach_make_memory_entry_64(mach_task_self(), &mos, vm_addr, flags, 544 &mep, MACH_PORT_NULL); 545 } 546 if (dispatch_assume_zero(kr)) { 547 mep = MACH_PORT_NULL; 548 } else if (mos < vm_size) { 549 // Memory object was truncated, e.g. due to lack of MAP_MEM_VM_COPY 550 kr = mach_port_deallocate(mach_task_self(), mep); 551 (void)dispatch_assume_zero(kr); 552 if (!copy) { 553 copy = true; 554 goto retry; 555 } 556 mep = MACH_PORT_NULL; 557 } 558 if (copy) { 559 kr = mach_vm_deallocate(mach_task_self(), vm_addr, vm_size); 560 (void)dispatch_assume_zero(kr); 561 } 562 return mep; 563} 564#endif // HAVE_MACH 565