~ubuntu-branches/ubuntu/maverick/pdns/maverick-updates : revision 13

1

/*

2

This is a version (aka dlmalloc) of malloc/free/realloc written by

3

Doug Lea and released to the public domain, as explained at

4

http://creativecommons.org/licenses/publicdomain. Send questions,

5

comments, complaints, performance data, etc to dl@cs.oswego.edu

6

7

* Version 2.8.3 Thu Sep 22 11:16:15 2005 Doug Lea (dl at gee)

8

9

Note: There may be an updated version of this malloc obtainable at

10

ftp://gee.cs.oswego.edu/pub/misc/malloc.c

11

Check before installing!

12

13

* Quickstart

14

15

This library is all in one file to simplify the most common usage:

16

ftp it, compile it (-O3), and link it into another program. All of

17

the compile-time options default to reasonable values for use on

18

most platforms. You might later want to step through various

19

compile-time and dynamic tuning options.

20

21

For convenience, an include file for code using this malloc is at:

22

ftp://gee.cs.oswego.edu/pub/misc/malloc-2.8.3.h

23

You don't really need this .h file unless you call functions not

24

defined in your system include files. The .h file contains only the

25

excerpts from this file needed for using this malloc on ANSI C/C++

26

systems, so long as you haven't changed compile-time options about

27

naming and tuning parameters. If you do, then you can create your

28

own malloc.h that does include all settings by cutting at the point

29

indicated below. Note that you may already by default be using a C

30

library containing a malloc that is based on some version of this

31

malloc (for example in linux). You might still want to use the one

32

in this file to customize settings or to avoid overheads associated

33

with library versions.

34

35

* Vital statistics:

36

37

Supported pointer/size_t representation: 4 or 8 bytes

38

size_t MUST be an unsigned type of the same width as

39

pointers. (If you are using an ancient system that declares

40

size_t as a signed type, or need it to be a different width

41

than pointers, you can use a previous release of this malloc

42

(e.g. 2.7.2) supporting these.)

43

44

Alignment: 8 bytes (default)

45

This suffices for nearly all current machines and C compilers.

46

However, you can define MALLOC_ALIGNMENT to be wider than this

47

if necessary (up to 128bytes), at the expense of using more space.

48

49

Minimum overhead per allocated chunk: 4 or 8 bytes (if 4byte sizes)

50

8 or 16 bytes (if 8byte sizes)

51

Each malloced chunk has a hidden word of overhead holding size

52

and status information, and additional cross-check word

53

if FOOTERS is defined.

54

55

Minimum allocated size: 4-byte ptrs: 16 bytes (including overhead)

56

8-byte ptrs: 32 bytes (including overhead)

57

58

Even a request for zero bytes (i.e., malloc(0)) returns a

59

pointer to something of the minimum allocatable size.

60

The maximum overhead wastage (i.e., number of extra bytes

61

allocated than were requested in malloc) is less than or equal

62

to the minimum size, except for requests >= mmap_threshold that

63

are serviced via mmap(), where the worst case wastage is about

64

32 bytes plus the remainder from a system page (the minimal

65

mmap unit); typically 4096 or 8192 bytes.

66

67

Security: static-safe; optionally more or less

68

The "security" of malloc refers to the ability of malicious

69

code to accentuate the effects of errors (for example, freeing

70

space that is not currently malloc'ed or overwriting past the

71

ends of chunks) in code that calls malloc. This malloc

72

guarantees not to modify any memory locations below the base of

73

heap, i.e., static variables, even in the presence of usage

74

errors. The routines additionally detect most improper frees

75

and reallocs. All this holds as long as the static bookkeeping

76

for malloc itself is not corrupted by some other means. This

77

is only one aspect of security -- these checks do not, and

78

cannot, detect all possible programming errors.

79

80

If FOOTERS is defined nonzero, then each allocated chunk

81

carries an additional check word to verify that it was malloced

82

from its space. These check words are the same within each

83

execution of a program using malloc, but differ across

84

executions, so externally crafted fake chunks cannot be

85

freed. This improves security by rejecting frees/reallocs that

86

could corrupt heap memory, in addition to the checks preventing

87

writes to statics that are always on. This may further improve

88

security at the expense of time and space overhead. (Note that

89

FOOTERS may also be worth using with MSPACES.)

90

91

By default detected errors cause the program to abort (calling

92

"abort()"). You can override this to instead proceed past

93

errors by defining PROCEED_ON_ERROR. In this case, a bad free

94

has no effect, and a malloc that encounters a bad address

95

caused by user overwrites will ignore the bad address by

96

dropping pointers and indices to all known memory. This may

97

be appropriate for programs that should continue if at all

98

possible in the face of programming errors, although they may

99

run out of memory because dropped memory is never reclaimed.

100

101

If you don't like either of these options, you can define

102

CORRUPTION_ERROR_ACTION and USAGE_ERROR_ACTION to do anything

103

else. And if if you are sure that your program using malloc has

104

no errors or vulnerabilities, you can define INSECURE to 1,

105

which might (or might not) provide a small performance improvement.

106

107

Thread-safety: NOT thread-safe unless USE_LOCKS defined

108

When USE_LOCKS is defined, each public call to malloc, free,

109

etc is surrounded with either a pthread mutex or a win32

110

spinlock (depending on WIN32). This is not especially fast, and

111

can be a major bottleneck. It is designed only to provide

112

minimal protection in concurrent environments, and to provide a

113

basis for extensions. If you are using malloc in a concurrent

114

program, consider instead using ptmalloc, which is derived from

115

a version of this malloc. (See http://www.malloc.de).

116

117

System requirements: Any combination of MORECORE and/or MMAP/MUNMAP

118

This malloc can use unix sbrk or any emulation (invoked using

119

the CALL_MORECORE macro) and/or mmap/munmap or any emulation

120

(invoked using CALL_MMAP/CALL_MUNMAP) to get and release system

121

memory. On most unix systems, it tends to work best if both

122

MORECORE and MMAP are enabled. On Win32, it uses emulations

123

based on VirtualAlloc. It also uses common C library functions

124

like memset.

125

126

Compliance: I believe it is compliant with the Single Unix Specification

127

(See http://www.unix.org). Also SVID/XPG, ANSI C, and probably

128

others as well.

129

130

* Overview of algorithms

131

132

This is not the fastest, most space-conserving, most portable, or

133

most tunable malloc ever written. However it is among the fastest

134

while also being among the most space-conserving, portable and

135

tunable. Consistent balance across these factors results in a good

136

general-purpose allocator for malloc-intensive programs.

137

138

In most ways, this malloc is a best-fit allocator. Generally, it

139

chooses the best-fitting existing chunk for a request, with ties

140

broken in approximately least-recently-used order. (This strategy

141

normally maintains low fragmentation.) However, for requests less

142

than 256bytes, it deviates from best-fit when there is not an

143

exactly fitting available chunk by preferring to use space adjacent

144

to that used for the previous small request, as well as by breaking

145

ties in approximately most-recently-used order. (These enhance

146

locality of series of small allocations.) And for very large requests

147

(>= 256Kb by default), it relies on system memory mapping

148

facilities, if supported. (This helps avoid carrying around and

149

possibly fragmenting memory used only for large chunks.)

150

151

All operations (except malloc_stats and mallinfo) have execution

152

times that are bounded by a constant factor of the number of bits in

153

a size_t, not counting any clearing in calloc or copying in realloc,

154

or actions surrounding MORECORE and MMAP that have times

155

proportional to the number of non-contiguous regions returned by

156

system allocation routines, which is often just 1.

157

158

The implementation is not very modular and seriously overuses

159

macros. Perhaps someday all C compilers will do as good a job

160

inlining modular code as can now be done by brute-force expansion,

161

but now, enough of them seem not to.

162

163

Some compilers issue a lot of warnings about code that is

164

dead/unreachable only on some platforms, and also about intentional

165

uses of negation on unsigned types. All known cases of each can be

166

ignored.

167

168

For a longer but out of date high-level description, see

169

http://gee.cs.oswego.edu/dl/html/malloc.html

170

171

* MSPACES

172

If MSPACES is defined, then in addition to malloc, free, etc.,

173

this file also defines mspace_malloc, mspace_free, etc. These

174

are versions of malloc routines that take an "mspace" argument

175

obtained using create_mspace, to control all internal bookkeeping.

176

If ONLY_MSPACES is defined, only these versions are compiled.

177

So if you would like to use this allocator for only some allocations,

178

and your system malloc for others, you can compile with

179

ONLY_MSPACES and then do something like...

180

static mspace mymspace = create_mspace(0,0); // for example

181

#define mymalloc(bytes) mspace_malloc(mymspace, bytes)

182

183

(Note: If you only need one instance of an mspace, you can instead

184

use "USE_DL_PREFIX" to relabel the global malloc.)

185

186

You can similarly create thread-local allocators by storing

187

mspaces as thread-locals. For example:

188

static __thread mspace tlms = 0;

189

void* tlmalloc(size_t bytes) {

190

if (tlms == 0) tlms = create_mspace(0, 0);

191

return mspace_malloc(tlms, bytes);

192

}

193

void tlfree(void* mem) { mspace_free(tlms, mem); }

194

195

Unless FOOTERS is defined, each mspace is completely independent.

196

You cannot allocate from one and free to another (although

197

conformance is only weakly checked, so usage errors are not always

198

caught). If FOOTERS is defined, then each chunk carries around a tag

199

indicating its originating mspace, and frees are directed to their

200

originating spaces.

201

202

------------------------- Compile-time options ---------------------------

203

204

Be careful in setting #define values for numerical constants of type

205

size_t. On some systems, literal values are not automatically extended

206

to size_t precision unless they are explicitly casted.

207

208

WIN32 default: defined if _WIN32 defined

209

Defining WIN32 sets up defaults for MS environment and compilers.

210

Otherwise defaults are for unix.

211

212

MALLOC_ALIGNMENT default: (size_t)8

213

Controls the minimum alignment for malloc'ed chunks. It must be a

214

power of two and at least 8, even on machines for which smaller

215

alignments would suffice. It may be defined as larger than this

216

though. Note however that code and data structures are optimized for

217

the case of 8-byte alignment.

218

219

MSPACES default: 0 (false)

220

If true, compile in support for independent allocation spaces.

221

This is only supported if HAVE_MMAP is true.

222

223

ONLY_MSPACES default: 0 (false)

224

If true, only compile in mspace versions, not regular versions.

225

226

USE_LOCKS default: 0 (false)

227

Causes each call to each public routine to be surrounded with

228

pthread or WIN32 mutex lock/unlock. (If set true, this can be

229

overridden on a per-mspace basis for mspace versions.)

230

231

FOOTERS default: 0

232

If true, provide extra checking and dispatching by placing

233

information in the footers of allocated chunks. This adds

234

space and time overhead.

235

236

INSECURE default: 0

237

If true, omit checks for usage errors and heap space overwrites.

238

239

USE_DL_PREFIX default: NOT defined

240

Causes compiler to prefix all public routines with the string 'dl'.

241

This can be useful when you only want to use this malloc in one part

242

of a program, using your regular system malloc elsewhere.

243

244

ABORT default: defined as abort()

245

Defines how to abort on failed checks. On most systems, a failed

246

check cannot die with an "assert" or even print an informative

247

message, because the underlying print routines in turn call malloc,

248

which will fail again. Generally, the best policy is to simply call

249

abort(). It's not very useful to do more than this because many

250

errors due to overwriting will show up as address faults (null, odd

251

addresses etc) rather than malloc-triggered checks, so will also

252

abort. Also, most compilers know that abort() does not return, so

253

can better optimize code conditionally calling it.

254

255

PROCEED_ON_ERROR default: defined as 0 (false)

256

Controls whether detected bad addresses cause them to bypassed

257

rather than aborting. If set, detected bad arguments to free and

258

realloc are ignored. And all bookkeeping information is zeroed out

259

upon a detected overwrite of freed heap space, thus losing the

260

ability to ever return it from malloc again, but enabling the

261

application to proceed. If PROCEED_ON_ERROR is defined, the

262

static variable malloc_corruption_error_count is compiled in

263

and can be examined to see if errors have occurred. This option

264

generates slower code than the default abort policy.

265

266

DEBUG default: NOT defined

267

The DEBUG setting is mainly intended for people trying to modify

268

this code or diagnose problems when porting to new platforms.

269

However, it may also be able to better isolate user errors than just

270

using runtime checks. The assertions in the check routines spell

271

out in more detail the assumptions and invariants underlying the

272

algorithms. The checking is fairly extensive, and will slow down

273

execution noticeably. Calling malloc_stats or mallinfo with DEBUG

274

set will attempt to check every non-mmapped allocated and free chunk

275

in the course of computing the summaries.

276

277

ABORT_ON_ASSERT_FAILURE default: defined as 1 (true)

278

Debugging assertion failures can be nearly impossible if your

279

version of the assert macro causes malloc to be called, which will

280

lead to a cascade of further failures, blowing the runtime stack.

281

ABORT_ON_ASSERT_FAILURE cause assertions failures to call abort(),

282

which will usually make debugging easier.

283

284

MALLOC_FAILURE_ACTION default: sets errno to ENOMEM, or no-op on win32

285

The action to take before "return 0" when malloc fails to be able to

286

return memory because there is none available.

287

288

HAVE_MORECORE default: 1 (true) unless win32 or ONLY_MSPACES

289

True if this system supports sbrk or an emulation of it.

290

291

MORECORE default: sbrk

292

The name of the sbrk-style system routine to call to obtain more

293

memory. See below for guidance on writing custom MORECORE

294

functions. The type of the argument to sbrk/MORECORE varies across

295

systems. It cannot be size_t, because it supports negative

296

arguments, so it is normally the signed type of the same width as

297

size_t (sometimes declared as "intptr_t"). It doesn't much matter

298

though. Internally, we only call it with arguments less than half

299

the max value of a size_t, which should work across all reasonable

300

possibilities, although sometimes generating compiler warnings. See

301

near the end of this file for guidelines for creating a custom

302

version of MORECORE.

303

304

MORECORE_CONTIGUOUS default: 1 (true)

305

If true, take advantage of fact that consecutive calls to MORECORE

306

with positive arguments always return contiguous increasing

307

addresses. This is true of unix sbrk. It does not hurt too much to

308

set it true anyway, since malloc copes with non-contiguities.

309

Setting it false when definitely non-contiguous saves time

310

and possibly wasted space it would take to discover this though.

311

312

MORECORE_CANNOT_TRIM default: NOT defined

313

True if MORECORE cannot release space back to the system when given

314

negative arguments. This is generally necessary only if you are

315

using a hand-crafted MORECORE function that cannot handle negative

316

arguments.

317

318

DONT_MERGE_SEGMENTS default: NOT defined

319

Defined if no attempt should be made to merge memory segments

320

returned by either MORECORE or CALL_MMAP. This is mostly an

321

optimization step to avoid having to walk through all the memory

322

segments when it is known in advance that a merge will not be possible.

323

324

HAVE_MMAP default: 1 (true)

325

True if this system supports mmap or an emulation of it. If so, and

326

HAVE_MORECORE is not true, MMAP is used for all system

327

allocation. If set and HAVE_MORECORE is true as well, MMAP is

328

primarily used to directly allocate very large blocks. It is also

329

used as a backup strategy in cases where MORECORE fails to provide

330

space from system. Note: A single call to MUNMAP is assumed to be

331

able to unmap memory that may have be allocated using multiple calls

332

to MMAP, so long as they are adjacent.

333

334

HAVE_MREMAP default: 1 on linux, else 0

335

If true realloc() uses mremap() to re-allocate large blocks and

336

extend or shrink allocation spaces.

337

338

MMAP_CLEARS default: 1 on unix

339

True if mmap clears memory so calloc doesn't need to. This is true

340

for standard unix mmap using /dev/zero.

341

342

USE_BUILTIN_FFS default: 0 (i.e., not used)

343

Causes malloc to use the builtin ffs() function to compute indices.

344

Some compilers may recognize and intrinsify ffs to be faster than the

345

supplied C version. Also, the case of x86 using gcc is special-cased

346

to an asm instruction, so is already as fast as it can be, and so

347

this setting has no effect. (On most x86s, the asm version is only

348

slightly faster than the C version.)

349

350

malloc_getpagesize default: derive from system includes, or 4096.

351

The system page size. To the extent possible, this malloc manages

352

memory from the system in page-size units. This may be (and

353

usually is) a function rather than a constant. This is ignored

354

if WIN32, where page size is determined using getSystemInfo during

355

initialization.

356

357

USE_DEV_RANDOM default: 0 (i.e., not used)

358

Causes malloc to use /dev/random to initialize secure magic seed for

359

stamping footers. Otherwise, the current time is used.

360

361

NO_MALLINFO default: 0

362

If defined, don't compile "mallinfo". This can be a simple way

363

of dealing with mismatches between system declarations and

364

those in this file.

365

366

MALLINFO_FIELD_TYPE default: size_t

367

The type of the fields in the mallinfo struct. This was originally

368

defined as "int" in SVID etc, but is more usefully defined as

369

size_t. The value is used only if HAVE_USR_INCLUDE_MALLOC_H is not set

370

371

REALLOC_ZERO_BYTES_FREES default: not defined

372

This should be set if a call to realloc with zero bytes should

373

be the same as a call to free. Some people think it should. Otherwise,

374

since this malloc returns a unique pointer for malloc(0), so does

375

realloc(p, 0).

376

377

LACKS_UNISTD_H, LACKS_FCNTL_H, LACKS_SYS_PARAM_H, LACKS_SYS_MMAN_H

378

LACKS_STRINGS_H, LACKS_STRING_H, LACKS_SYS_TYPES_H, LACKS_ERRNO_H

379

LACKS_STDLIB_H default: NOT defined unless on WIN32

380

Define these if your system does not have these header files.

381

You might need to manually insert some of the declarations they provide.

382

383

DEFAULT_GRANULARITY default: page size if MORECORE_CONTIGUOUS,

384

system_info.dwAllocationGranularity in WIN32,

385

otherwise 64K.

386

Also settable using mallopt(M_GRANULARITY, x)

387

The unit for allocating and deallocating memory from the system. On

388

most systems with contiguous MORECORE, there is no reason to

389

make this more than a page. However, systems with MMAP tend to

390

either require or encourage larger granularities. You can increase

391

this value to prevent system allocation functions to be called so

392

often, especially if they are slow. The value must be at least one

393

page and must be a power of two. Setting to 0 causes initialization

394

to either page size or win32 region size. (Note: In previous

395

versions of malloc, the equivalent of this option was called

396

"TOP_PAD")

397

398

DEFAULT_TRIM_THRESHOLD default: 2MB

399

Also settable using mallopt(M_TRIM_THRESHOLD, x)

400

The maximum amount of unused top-most memory to keep before

401

releasing via malloc_trim in free(). Automatic trimming is mainly

402

useful in long-lived programs using contiguous MORECORE. Because

403

trimming via sbrk can be slow on some systems, and can sometimes be

404

wasteful (in cases where programs immediately afterward allocate

405

more large chunks) the value should be high enough so that your

406

overall system performance would improve by releasing this much

407

memory. As a rough guide, you might set to a value close to the

408

average size of a process (program) running on your system.

409

Releasing this much memory would allow such a process to run in

410

memory. Generally, it is worth tuning trim thresholds when a

411

program undergoes phases where several large chunks are allocated

412

and released in ways that can reuse each other's storage, perhaps

413

mixed with phases where there are no such chunks at all. The trim

414

value must be greater than page size to have any useful effect. To

415

disable trimming completely, you can set to MAX_SIZE_T. Note that the trick

416

some people use of mallocing a huge space and then freeing it at

417

program startup, in an attempt to reserve system memory, doesn't

418

have the intended effect under automatic trimming, since that memory

419

will immediately be returned to the system.

420

421

DEFAULT_MMAP_THRESHOLD default: 256K

422

Also settable using mallopt(M_MMAP_THRESHOLD, x)

423

The request size threshold for using MMAP to directly service a

424

request. Requests of at least this size that cannot be allocated

425

using already-existing space will be serviced via mmap. (If enough

426

normal freed space already exists it is used instead.) Using mmap

427

segregates relatively large chunks of memory so that they can be

428

individually obtained and released from the host system. A request

429

serviced through mmap is never reused by any other request (at least

430

not directly; the system may just so happen to remap successive

431

requests to the same locations). Segregating space in this way has

432

the benefits that: Mmapped space can always be individually released

433

back to the system, which helps keep the system level memory demands

434

of a long-lived program low. Also, mapped memory doesn't become

435

`locked' between other chunks, as can happen with normally allocated

436

chunks, which means that even trimming via malloc_trim would not

437

release them. However, it has the disadvantage that the space

438

cannot be reclaimed, consolidated, and then used to service later

439

requests, as happens with normal chunks. The advantages of mmap

440

nearly always outweigh disadvantages for "large" chunks, but the

441

value of "large" may vary across systems. The default is an

442

empirically derived value that works well in most systems. You can

443

disable mmap by setting to MAX_SIZE_T.

444

445

*/

446

447

#ifndef WIN32

448

#ifdef _WIN32

449

#define WIN32 1

450

#endif /* _WIN32 */

451

#endif /* WIN32 */

452

#ifdef WIN32

453

#define WIN32_LEAN_AND_MEAN

454

#include <windows.h>

455

#define HAVE_MMAP 1

456

#define HAVE_MORECORE 0

457

#define LACKS_UNISTD_H

458

#define LACKS_SYS_PARAM_H

459

#define LACKS_SYS_MMAN_H

460

#define LACKS_STRING_H

461

#define LACKS_STRINGS_H

462

#define LACKS_SYS_TYPES_H

463

#define LACKS_ERRNO_H

464

#define MALLOC_FAILURE_ACTION

465

#define MMAP_CLEARS 1 /* WINCE and some others apparently don't clear */

466

#endif /* WIN32 */

467

468

#if defined(DARWIN) || defined(_DARWIN)

469

/* Mac OSX docs advise not to use sbrk; it seems better to use mmap */

470

#ifndef HAVE_MORECORE

471

#define HAVE_MORECORE 0

472

#define HAVE_MMAP 1

473

#endif /* HAVE_MORECORE */

474

#endif /* DARWIN */

475

476

#ifndef LACKS_SYS_TYPES_H

477

#include <sys/types.h> /* For size_t */

478

#endif /* LACKS_SYS_TYPES_H */

479

480

/* The maximum possible size_t value has all bits set */

481

#define MAX_SIZE_T (~(size_t)0)

482

483

#ifndef ONLY_MSPACES

484

#define ONLY_MSPACES 0

485

#endif /* ONLY_MSPACES */

486

#ifndef MSPACES

487

#if ONLY_MSPACES

488

#define MSPACES 1

489

#else /* ONLY_MSPACES */

490

#define MSPACES 0

491

#endif /* ONLY_MSPACES */

492

#endif /* MSPACES */

493

#ifndef MALLOC_ALIGNMENT

494

#define MALLOC_ALIGNMENT ((size_t)8U)

495

#endif /* MALLOC_ALIGNMENT */

496

#ifndef FOOTERS

497

#define FOOTERS 0

498

#endif /* FOOTERS */

499

#ifndef ABORT

500

#define ABORT abort()

501

#endif /* ABORT */

502

#ifndef ABORT_ON_ASSERT_FAILURE

503

#define ABORT_ON_ASSERT_FAILURE 1

504

#endif /* ABORT_ON_ASSERT_FAILURE */

505

#ifndef PROCEED_ON_ERROR

506

#define PROCEED_ON_ERROR 0

507

#endif /* PROCEED_ON_ERROR */

508

#ifndef USE_LOCKS

509

#define USE_LOCKS 0

510

#endif /* USE_LOCKS */

511

#ifndef INSECURE

512

#define INSECURE 0

513

#endif /* INSECURE */

514

#ifndef HAVE_MMAP

515

#define HAVE_MMAP 1

516

#endif /* HAVE_MMAP */

517

#ifndef MMAP_CLEARS

518

#define MMAP_CLEARS 1

519

#endif /* MMAP_CLEARS */

520

#ifndef HAVE_MREMAP

521

#ifdef linux

522

#define HAVE_MREMAP 1

523

#else /* linux */

524

#define HAVE_MREMAP 0

525

#endif /* linux */

526

#endif /* HAVE_MREMAP */

527

#ifndef MALLOC_FAILURE_ACTION

528

#define MALLOC_FAILURE_ACTION errno = ENOMEM;

529

#endif /* MALLOC_FAILURE_ACTION */

530

#ifndef HAVE_MORECORE

531

#if ONLY_MSPACES

532

#define HAVE_MORECORE 0

533

#else /* ONLY_MSPACES */

534

#define HAVE_MORECORE 1

535

#endif /* ONLY_MSPACES */

536

#endif /* HAVE_MORECORE */

537

#if !HAVE_MORECORE

538

#define MORECORE_CONTIGUOUS 0

539

#else /* !HAVE_MORECORE */

540

#ifndef MORECORE

541

#define MORECORE sbrk

542

#endif /* MORECORE */

543

#ifndef MORECORE_CONTIGUOUS

544

#define MORECORE_CONTIGUOUS 1

545

#endif /* MORECORE_CONTIGUOUS */

546

#endif /* HAVE_MORECORE */

547

#ifndef DEFAULT_GRANULARITY

548

#if MORECORE_CONTIGUOUS

549

#define DEFAULT_GRANULARITY (0) /* 0 means to compute in init_mparams */

550

#else /* MORECORE_CONTIGUOUS */

551

#define DEFAULT_GRANULARITY ((size_t)64U * (size_t)1024U)

552

#endif /* MORECORE_CONTIGUOUS */

553

#endif /* DEFAULT_GRANULARITY */

554

#ifndef DEFAULT_TRIM_THRESHOLD

555

#ifndef MORECORE_CANNOT_TRIM

556

#define DEFAULT_TRIM_THRESHOLD ((size_t)2U * (size_t)1024U * (size_t)1024U)

557

#else /* MORECORE_CANNOT_TRIM */

558

#define DEFAULT_TRIM_THRESHOLD MAX_SIZE_T

559

#endif /* MORECORE_CANNOT_TRIM */

560

#endif /* DEFAULT_TRIM_THRESHOLD */

561

#ifndef DEFAULT_MMAP_THRESHOLD

562

#if HAVE_MMAP

563

#define DEFAULT_MMAP_THRESHOLD ((size_t)256U * (size_t)1024U)

564

#else /* HAVE_MMAP */

565

#define DEFAULT_MMAP_THRESHOLD MAX_SIZE_T

566

#endif /* HAVE_MMAP */

567

#endif /* DEFAULT_MMAP_THRESHOLD */

568

#ifndef USE_BUILTIN_FFS

569

#define USE_BUILTIN_FFS 0

570

#endif /* USE_BUILTIN_FFS */

571

#ifndef USE_DEV_RANDOM

572

#define USE_DEV_RANDOM 0

573

#endif /* USE_DEV_RANDOM */

574

#ifndef NO_MALLINFO

575

#define NO_MALLINFO 0

576

#endif /* NO_MALLINFO */

577

#ifndef MALLINFO_FIELD_TYPE

578

#define MALLINFO_FIELD_TYPE size_t

579

#endif /* MALLINFO_FIELD_TYPE */

580

581

/*

582

mallopt tuning options. SVID/XPG defines four standard parameter

583

numbers for mallopt, normally defined in malloc.h. None of these

584

are used in this malloc, so setting them has no effect. But this

585

malloc does support the following options.

586

*/

587

588

#define M_TRIM_THRESHOLD (-1)

589

#define M_GRANULARITY (-2)

590

#define M_MMAP_THRESHOLD (-3)

591

592

/* ------------------------ Mallinfo declarations ------------------------ */

593

594

#if !NO_MALLINFO

595

/*

596

This version of malloc supports the standard SVID/XPG mallinfo

597

routine that returns a struct containing usage properties and

598

statistics. It should work on any system that has a

599

/usr/include/malloc.h defining struct mallinfo. The main

600

declaration needed is the mallinfo struct that is returned (by-copy)

601

by mallinfo(). The malloinfo struct contains a bunch of fields that

602

are not even meaningful in this version of malloc. These fields are

603

are instead filled by mallinfo() with other numbers that might be of

604

interest.

605

606

HAVE_USR_INCLUDE_MALLOC_H should be set if you have a

607

/usr/include/malloc.h file that includes a declaration of struct

608

mallinfo. If so, it is included; else a compliant version is

609

declared below. These must be precisely the same for mallinfo() to

610

work. The original SVID version of this struct, defined on most

611

systems with mallinfo, declares all fields as ints. But some others

612

define as unsigned long. If your system defines the fields using a

613

type of different width than listed here, you MUST #include your

614

system version and #define HAVE_USR_INCLUDE_MALLOC_H.

615

*/

616

617

/* #define HAVE_USR_INCLUDE_MALLOC_H */

618

619

#ifdef HAVE_USR_INCLUDE_MALLOC_H

620

#include "/usr/include/malloc.h"

621

#else /* HAVE_USR_INCLUDE_MALLOC_H */

622

623

struct mallinfo {

624

MALLINFO_FIELD_TYPE arena; /* non-mmapped space allocated from system */

625

MALLINFO_FIELD_TYPE ordblks; /* number of free chunks */

626

MALLINFO_FIELD_TYPE smblks; /* always 0 */

627

MALLINFO_FIELD_TYPE hblks; /* always 0 */

628

MALLINFO_FIELD_TYPE hblkhd; /* space in mmapped regions */

629

MALLINFO_FIELD_TYPE usmblks; /* maximum total allocated space */

630

MALLINFO_FIELD_TYPE fsmblks; /* always 0 */

631

MALLINFO_FIELD_TYPE uordblks; /* total allocated space */

632

MALLINFO_FIELD_TYPE fordblks; /* total free space */

633

MALLINFO_FIELD_TYPE keepcost; /* releasable (via malloc_trim) space */

634

};

635

636

#endif /* HAVE_USR_INCLUDE_MALLOC_H */

637

#endif /* NO_MALLINFO */

638

639

#ifndef FORCEINLINE

640

#if defined(__GNUC__)

641

#define FORCEINLINE __inline __attribute__ ((always_inline))

642

#elif defined(_MSC_VER)

643

#define FORCEINLINE __forceinline

644

#endif

645

#endif

646

#ifndef NOINLINE

647

#if defined(__GNUC__)

648

#define NOINLINE __attribute__ ((noinline))

649

#elif defined(_MSC_VER)

650

#define NOINLINE __declspec(noinline)

651

#else

652

#define NOINLINE

653

#endif

654

#endif

655

656

#ifdef __cplusplus

657

extern "C" {

658

#ifndef FORCEINLINE

659

#define FORCEINLINE inline

660

#endif

661

#endif /* __cplusplus */

662

#ifndef FORCEINLINE

663

#define FORCEINLINE

664

#endif

665

666

#if !ONLY_MSPACES

667

668

/* ------------------- Declarations of public routines ------------------- */

669

670

#ifndef USE_DL_PREFIX

671

#define dlcalloc calloc

672

#define dlfree free

673

#define dlmalloc malloc

674

#define dlmemalign memalign

675

#define dlrealloc realloc

676

#define dlvalloc valloc

677

#define dlpvalloc pvalloc

678

#define dlmallinfo mallinfo

679

#define dlmallopt mallopt

680

#define dlmalloc_trim malloc_trim

681

#define dlmalloc_stats malloc_stats

682

#define dlmalloc_usable_size malloc_usable_size

683

#define dlmalloc_footprint malloc_footprint

684

#define dlmalloc_max_footprint malloc_max_footprint

685

#define dlindependent_calloc independent_calloc

686

#define dlindependent_comalloc independent_comalloc

687

#endif /* USE_DL_PREFIX */

688

689

690

/*

691

malloc(size_t n)

692

Returns a pointer to a newly allocated chunk of at least n bytes, or

693

null if no space is available, in which case errno is set to ENOMEM

694

on ANSI C systems.

695

696

If n is zero, malloc returns a minimum-sized chunk. (The minimum

697

size is 16 bytes on most 32bit systems, and 32 bytes on 64bit

698

systems.) Note that size_t is an unsigned type, so calls with

699

arguments that would be negative if signed are interpreted as

700

requests for huge amounts of space, which will often fail. The

701

maximum supported value of n differs across systems, but is in all

702

cases less than the maximum representable value of a size_t.

703

*/

704

void* dlmalloc(size_t);

705

706

/*

707

free(void* p)

708

Releases the chunk of memory pointed to by p, that had been previously

709

allocated using malloc or a related routine such as realloc.

710

It has no effect if p is null. If p was not malloced or already

711

freed, free(p) will by default cause the current program to abort.

712

*/

713

void dlfree(void*);

714

715

/*

716

calloc(size_t n_elements, size_t element_size);

717

Returns a pointer to n_elements * element_size bytes, with all locations

718

set to zero.

719

*/

720

void* dlcalloc(size_t, size_t);

721

722

/*

723

realloc(void* p, size_t n)

724

Returns a pointer to a chunk of size n that contains the same data

725

as does chunk p up to the minimum of (n, p's size) bytes, or null

726

if no space is available.

727

728

The returned pointer may or may not be the same as p. The algorithm

729

prefers extending p in most cases when possible, otherwise it

730

employs the equivalent of a malloc-copy-free sequence.

731

732

If p is null, realloc is equivalent to malloc.

733

734

If space is not available, realloc returns null, errno is set (if on

735

ANSI) and p is NOT freed.

736

737

if n is for fewer bytes than already held by p, the newly unused

738

space is lopped off and freed if possible. realloc with a size

739

argument of zero (re)allocates a minimum-sized chunk.

740

741

The old unix realloc convention of allowing the last-free'd chunk

742

to be used as an argument to realloc is not supported.

743

*/

744

745

void* dlrealloc(void*, size_t);

746

747

/*

748

memalign(size_t alignment, size_t n);

749

Returns a pointer to a newly allocated chunk of n bytes, aligned

750

in accord with the alignment argument.

751

752

The alignment argument should be a power of two. If the argument is

753

not a power of two, the nearest greater power is used.

754

8-byte alignment is guaranteed by normal malloc calls, so don't

755

bother calling memalign with an argument of 8 or less.

756

757

Overreliance on memalign is a sure way to fragment space.

758

*/

759

void* dlmemalign(size_t, size_t);

760

761

/*

762

valloc(size_t n);

763

Equivalent to memalign(pagesize, n), where pagesize is the page

764

size of the system. If the pagesize is unknown, 4096 is used.

765

*/

766

void* dlvalloc(size_t);

767

768

/*

769

mallopt(int parameter_number, int parameter_value)

770

Sets tunable parameters The format is to provide a

771

(parameter-number, parameter-value) pair. mallopt then sets the

772

corresponding parameter to the argument value if it can (i.e., so

773

long as the value is meaningful), and returns 1 if successful else

774

0. SVID/XPG/ANSI defines four standard param numbers for mallopt,

775

normally defined in malloc.h. None of these are use in this malloc,

776

so setting them has no effect. But this malloc also supports other

777

options in mallopt. See below for details. Briefly, supported

778

parameters are as follows (listed defaults are for "typical"

779

configurations).

780

781

Symbol param # default allowed param values

782

M_TRIM_THRESHOLD -1 2*1024*1024 any (MAX_SIZE_T disables)

783

M_GRANULARITY -2 page size any power of 2 >= page size

784

M_MMAP_THRESHOLD -3 256*1024 any (or 0 if no MMAP support)

785

*/

786

int dlmallopt(int, int);

787

788

/*

789

malloc_footprint();

790

Returns the number of bytes obtained from the system. The total

791

number of bytes allocated by malloc, realloc etc., is less than this

792

value. Unlike mallinfo, this function returns only a precomputed

793

result, so can be called frequently to monitor memory consumption.

794

Even if locks are otherwise defined, this function does not use them,

795

so results might not be up to date.

796

*/

797

size_t dlmalloc_footprint(void);

798

799

/*

800

malloc_max_footprint();

801

Returns the maximum number of bytes obtained from the system. This

802

value will be greater than current footprint if deallocated space

803

has been reclaimed by the system. The peak number of bytes allocated

804

by malloc, realloc etc., is less than this value. Unlike mallinfo,

805

this function returns only a precomputed result, so can be called

806

frequently to monitor memory consumption. Even if locks are

807

otherwise defined, this function does not use them, so results might

808

not be up to date.

809

*/

810

size_t dlmalloc_max_footprint(void);

811

812

#if !NO_MALLINFO

813

/*

814

mallinfo()

815

Returns (by copy) a struct containing various summary statistics:

816

817

arena: current total non-mmapped bytes allocated from system

818

ordblks: the number of free chunks

819

smblks: always zero.

820

hblks: current number of mmapped regions

821

hblkhd: total bytes held in mmapped regions

822

usmblks: the maximum total allocated space. This will be greater

823

than current total if trimming has occurred.

824

fsmblks: always zero

825

uordblks: current total allocated space (normal or mmapped)

826

fordblks: total free space

827

keepcost: the maximum number of bytes that could ideally be released

828

back to system via malloc_trim. ("ideally" means that

829

it ignores page restrictions etc.)

830

831

Because these fields are ints, but internal bookkeeping may

832

be kept as longs, the reported values may wrap around zero and

833

thus be inaccurate.

834

*/

835

struct mallinfo dlmallinfo(void);

836

#endif /* NO_MALLINFO */

837

838

/*

839

independent_calloc(size_t n_elements, size_t element_size, void* chunks[]);

840

841

independent_calloc is similar to calloc, but instead of returning a

842

single cleared space, it returns an array of pointers to n_elements

843

independent elements that can hold contents of size elem_size, each

844

of which starts out cleared, and can be independently freed,

845

realloc'ed etc. The elements are guaranteed to be adjacently

846

allocated (this is not guaranteed to occur with multiple callocs or

847

mallocs), which may also improve cache locality in some

848

applications.

849

850

The "chunks" argument is optional (i.e., may be null, which is

851

probably the most typical usage). If it is null, the returned array

852

is itself dynamically allocated and should also be freed when it is

853

no longer needed. Otherwise, the chunks array must be of at least

854

n_elements in length. It is filled in with the pointers to the

855

chunks.

856

857

In either case, independent_calloc returns this pointer array, or

858

null if the allocation failed. If n_elements is zero and "chunks"

859

is null, it returns a chunk representing an array with zero elements

860

(which should be freed if not wanted).

861

862

Each element must be individually freed when it is no longer

863

needed. If you'd like to instead be able to free all at once, you

864

should instead use regular calloc and assign pointers into this

865

space to represent elements. (In this case though, you cannot

866

independently free elements.)

867

868

independent_calloc simplifies and speeds up implementations of many

869

kinds of pools. It may also be useful when constructing large data

870

structures that initially have a fixed number of fixed-sized nodes,

871

but the number is not known at compile time, and some of the nodes

872

may later need to be freed. For example:

873

874

struct Node { int item; struct Node* next; };

875

876

struct Node* build_list() {

877

struct Node** pool;

878

int n = read_number_of_nodes_needed();

879

if (n <= 0) return 0;

880

pool = (struct Node**)(independent_calloc(n, sizeof(struct Node), 0);

881

if (pool == 0) die();

882

// organize into a linked list...

883

struct Node* first = pool[0];

884

for (i = 0; i < n-1; ++i)

885

pool[i]->next = pool[i+1];

886

free(pool); // Can now free the array (or not, if it is needed later)

887

return first;

888

}

889

*/

890

void** dlindependent_calloc(size_t, size_t, void**);

891

892

/*

893

independent_comalloc(size_t n_elements, size_t sizes[], void* chunks[]);

894

895

independent_comalloc allocates, all at once, a set of n_elements

896

chunks with sizes indicated in the "sizes" array. It returns

897

an array of pointers to these elements, each of which can be

898

independently freed, realloc'ed etc. The elements are guaranteed to

899

be adjacently allocated (this is not guaranteed to occur with

900

multiple callocs or mallocs), which may also improve cache locality

901

in some applications.

902

903

The "chunks" argument is optional (i.e., may be null). If it is null

904

the returned array is itself dynamically allocated and should also

905

be freed when it is no longer needed. Otherwise, the chunks array

906

must be of at least n_elements in length. It is filled in with the

907

pointers to the chunks.

908

909

In either case, independent_comalloc returns this pointer array, or

910

null if the allocation failed. If n_elements is zero and chunks is

911

null, it returns a chunk representing an array with zero elements

912

(which should be freed if not wanted).

913

914

Each element must be individually freed when it is no longer

915

needed. If you'd like to instead be able to free all at once, you

916

should instead use a single regular malloc, and assign pointers at

917

particular offsets in the aggregate space. (In this case though, you

918

cannot independently free elements.)

919

920

independent_comallac differs from independent_calloc in that each

921

element may have a different size, and also that it does not

922

automatically clear elements.

923

924

independent_comalloc can be used to speed up allocation in cases

925

where several structs or objects must always be allocated at the

926

same time. For example:

927

928

struct Head { ... }

929

struct Foot { ... }

930

931

void send_message(char* msg) {

932

int msglen = strlen(msg);

933

size_t sizes[3] = { sizeof(struct Head), msglen, sizeof(struct Foot) };

934

void* chunks[3];

935

if (independent_comalloc(3, sizes, chunks) == 0)

936

die();

937

struct Head* head = (struct Head*)(chunks[0]);

938

char* body = (char*)(chunks[1]);

939

struct Foot* foot = (struct Foot*)(chunks[2]);

940

// ...

941

}

942

943

In general though, independent_comalloc is worth using only for

944

larger values of n_elements. For small values, you probably won't

945

detect enough difference from series of malloc calls to bother.

946

947

Overuse of independent_comalloc can increase overall memory usage,

948

since it cannot reuse existing noncontiguous small chunks that

949

might be available for some of the elements.

950

*/

951

void** dlindependent_comalloc(size_t, size_t*, void**);

952

953

954

/*

955

pvalloc(size_t n);

956

Equivalent to valloc(minimum-page-that-holds(n)), that is,

957

round up n to nearest pagesize.

958

*/

959

void* dlpvalloc(size_t);

960

961

/*

962

malloc_trim(size_t pad);

963

964

If possible, gives memory back to the system (via negative arguments

965

to sbrk) if there is unused memory at the `high' end of the malloc

966

pool or in unused MMAP segments. You can call this after freeing

967

large blocks of memory to potentially reduce the system-level memory

968

requirements of a program. However, it cannot guarantee to reduce

969

memory. Under some allocation patterns, some large free blocks of

970

memory will be locked between two used chunks, so they cannot be

971

given back to the system.

972

973

The `pad' argument to malloc_trim represents the amount of free

974

trailing space to leave untrimmed. If this argument is zero, only

975

the minimum amount of memory to maintain internal data structures

976

will be left. Non-zero arguments can be supplied to maintain enough

977

trailing space to service future expected allocations without having

978

to re-obtain memory from the system.

979

980

Malloc_trim returns 1 if it actually released any memory, else 0.

981

*/

982

int dlmalloc_trim(size_t);

983

984

/*

985

malloc_usable_size(void* p);

986

987

Returns the number of bytes you can actually use in

988

an allocated chunk, which may be more than you requested (although

989

often not) due to alignment and minimum size constraints.

990

You can use this many bytes without worrying about

991

overwriting other allocated objects. This is not a particularly great

992

programming practice. malloc_usable_size can be more useful in

993

debugging and assertions, for example:

994

995

p = malloc(n);

996

assert(malloc_usable_size(p) >= 256);

997

*/

998

size_t dlmalloc_usable_size(void*);

999

1000

/*

1001

malloc_stats();

1002

Prints on stderr the amount of space obtained from the system (both

1003

via sbrk and mmap), the maximum amount (which may be more than

1004

current if malloc_trim and/or munmap got called), and the current

1005

number of bytes allocated via malloc (or realloc, etc) but not yet

1006

freed. Note that this is the number of bytes allocated, not the

1007

number requested. It will be larger than the number requested

1008

because of alignment and bookkeeping overhead. Because it includes

1009

alignment wastage as being in use, this figure may be greater than

1010

zero even when no user-level chunks are allocated.

1011

1012

The reported current and maximum system memory can be inaccurate if

1013

a program makes other calls to system memory allocation functions

1014

(normally sbrk) outside of malloc.

1015

1016

malloc_stats prints only the most commonly interesting statistics.

1017

More information can be obtained by calling mallinfo.

1018

*/

1019

void dlmalloc_stats(void);

1020

1021

#endif /* ONLY_MSPACES */

1022

1023

#if MSPACES

1024

1025

/*

1026

mspace is an opaque type representing an independent

1027

region of space that supports mspace_malloc, etc.

1028

*/

1029

typedef void* mspace;

1030

1031

/*

1032

create_mspace creates and returns a new independent space with the

1033

given initial capacity, or, if 0, the default granularity size. It

1034

returns null if there is no system memory available to create the

1035

space. If argument locked is non-zero, the space uses a separate

1036

lock to control access. The capacity of the space will grow

1037

dynamically as needed to service mspace_malloc requests. You can

1038

control the sizes of incremental increases of this space by

1039

compiling with a different DEFAULT_GRANULARITY or dynamically

1040

setting with mallopt(M_GRANULARITY, value).

1041

*/

1042

mspace create_mspace(size_t capacity, int locked);

1043

1044

/*

1045

destroy_mspace destroys the given space, and attempts to return all

1046

of its memory back to the system, returning the total number of

1047

bytes freed. After destruction, the results of access to all memory

1048

used by the space become undefined.

1049

*/

1050

size_t destroy_mspace(mspace msp);

1051

1052

/*

1053

create_mspace_with_base uses the memory supplied as the initial base

1054

of a new mspace. Part (less than 128*sizeof(size_t) bytes) of this

1055

space is used for bookkeeping, so the capacity must be at least this

1056

large. (Otherwise 0 is returned.) When this initial space is

1057

exhausted, additional memory will be obtained from the system.

1058

Destroying this space will deallocate all additionally allocated

1059

space (if possible) but not the initial base.

1060

*/

1061

mspace create_mspace_with_base(void* base, size_t capacity, int locked);

1062

1063

/*

1064

mspace_malloc behaves as malloc, but operates within

1065

the given space.

1066

*/

1067

void* mspace_malloc(mspace msp, size_t bytes);

1068

1069

/*

1070

mspace_free behaves as free, but operates within

1071

the given space.

1072

1073

If compiled with FOOTERS==1, mspace_free is not actually needed.

1074

free may be called instead of mspace_free because freed chunks from

1075

any space are handled by their originating spaces.

1076

*/

1077

void mspace_free(mspace msp, void* mem);

1078

1079

/*

1080

mspace_realloc behaves as realloc, but operates within

1081

the given space.

1082

1083

If compiled with FOOTERS==1, mspace_realloc is not actually

1084

needed. realloc may be called instead of mspace_realloc because

1085

realloced chunks from any space are handled by their originating

1086

spaces.

1087

*/

1088

void* mspace_realloc(mspace msp, void* mem, size_t newsize);

1089

1090

/*

1091

mspace_calloc behaves as calloc, but operates within

1092

the given space.

1093

*/

1094

void* mspace_calloc(mspace msp, size_t n_elements, size_t elem_size);

1095

1096

/*

1097

mspace_memalign behaves as memalign, but operates within

1098

the given space.

1099

*/

1100

void* mspace_memalign(mspace msp, size_t alignment, size_t bytes);

1101

1102

/*

1103

mspace_independent_calloc behaves as independent_calloc, but

1104

operates within the given space.

1105

*/

1106

void** mspace_independent_calloc(mspace msp, size_t n_elements,

1107

size_t elem_size, void* chunks[]);

1108

1109

/*

1110

mspace_independent_comalloc behaves as independent_comalloc, but

1111

operates within the given space.

1112

*/

1113

void** mspace_independent_comalloc(mspace msp, size_t n_elements,

1114

size_t sizes[], void* chunks[]);

1115

1116

/*

1117

mspace_footprint() returns the number of bytes obtained from the

1118

system for this space.

1119

*/

1120

size_t mspace_footprint(mspace msp);

1121

1122

/*

1123

mspace_max_footprint() returns the peak number of bytes obtained from the

1124

system for this space.

1125

*/

1126

size_t mspace_max_footprint(mspace msp);

1127

1128

1129

#if !NO_MALLINFO

1130

/*

1131

mspace_mallinfo behaves as mallinfo, but reports properties of

1132

the given space.

1133

*/

1134

struct mallinfo mspace_mallinfo(mspace msp);

1135

#endif /* NO_MALLINFO */

1136

1137

/*

1138

mspace_malloc_stats behaves as malloc_stats, but reports

1139

properties of the given space.

1140

*/

1141

void mspace_malloc_stats(mspace msp);

1142

1143

/*

1144

mspace_trim behaves as malloc_trim, but

1145

operates within the given space.

1146

*/

1147

int mspace_trim(mspace msp, size_t pad);

1148

1149

/*

1150

An alias for mallopt.

1151

*/

1152

int mspace_mallopt(int, int);

1153

1154

#endif /* MSPACES */

1155

1156

#ifdef __cplusplus

1157

}; /* end of extern "C" */

1158

#endif /* __cplusplus */

1159

1160

/*

1161

========================================================================

1162

To make a fully customizable malloc.h header file, cut everything

1163

above this line, put into file malloc.h, edit to suit, and #include it

1164

on the next line, as well as in programs that use this malloc.

1165

========================================================================

1166

*/

1167

1168

/* #include "malloc.h" */

1169

1170

/*------------------------------ internal #includes ---------------------- */

1171

1172

#ifdef WIN32

1173

#pragma warning( disable : 4146 ) /* no "unsigned" warnings */

1174

#endif /* WIN32 */

1175

1176

#include <stdio.h> /* for printing in malloc_stats */

1177

1178

#ifndef LACKS_ERRNO_H

1179

#include <errno.h> /* for MALLOC_FAILURE_ACTION */

1180

#endif /* LACKS_ERRNO_H */

1181

#if FOOTERS

1182

#include <time.h> /* for magic initialization */

1183

#endif /* FOOTERS */

1184

#ifndef LACKS_STDLIB_H

1185

#include <stdlib.h> /* for abort() */

1186

#endif /* LACKS_STDLIB_H */

1187

#ifdef DEBUG

1188

#if ABORT_ON_ASSERT_FAILURE

1189

#define assert(x) if(!(x)) ABORT

1190

#else /* ABORT_ON_ASSERT_FAILURE */

1191

#include <assert.h>

1192

#endif /* ABORT_ON_ASSERT_FAILURE */

1193

#else /* DEBUG */

1194

#define assert(x)

1195

#endif /* DEBUG */

1196

#ifndef LACKS_STRING_H

1197

#include <string.h> /* for memset etc */

1198

#endif /* LACKS_STRING_H */

1199

#if USE_BUILTIN_FFS

1200

#ifndef LACKS_STRINGS_H

1201

#include <strings.h> /* for ffs */

1202

#endif /* LACKS_STRINGS_H */

1203

#endif /* USE_BUILTIN_FFS */

1204

#if HAVE_MMAP

1205

#ifndef LACKS_SYS_MMAN_H

1206

#include <sys/mman.h> /* for mmap */

1207

#endif /* LACKS_SYS_MMAN_H */

1208

#ifndef LACKS_FCNTL_H

1209

#include <fcntl.h>

1210

#endif /* LACKS_FCNTL_H */

1211

#endif /* HAVE_MMAP */

1212

#if HAVE_MORECORE

1213

#ifndef LACKS_UNISTD_H

1214

#include <unistd.h> /* for sbrk */

1215

#else /* LACKS_UNISTD_H */

1216

#if !defined(__FreeBSD__) && !defined(__OpenBSD__) && !defined(__NetBSD__)

1217

extern void* sbrk(ptrdiff_t);

1218

#endif /* FreeBSD etc */

1219

#endif /* LACKS_UNISTD_H */

1220

#endif /* HAVE_MMAP */

1221

1222

#ifndef WIN32

1223

#ifndef malloc_getpagesize

1224

# ifdef _SC_PAGESIZE /* some SVR4 systems omit an underscore */

1225

# ifndef _SC_PAGE_SIZE

1226

# define _SC_PAGE_SIZE _SC_PAGESIZE

1227

# endif

1228

# endif

1229

# ifdef _SC_PAGE_SIZE

1230

# define malloc_getpagesize sysconf(_SC_PAGE_SIZE)

1231

# else

1232

# if defined(BSD) || defined(DGUX) || defined(HAVE_GETPAGESIZE)

1233

extern size_t getpagesize();

1234

# define malloc_getpagesize getpagesize()

1235

# else

1236

# ifdef WIN32 /* use supplied emulation of getpagesize */

1237

# define malloc_getpagesize getpagesize()

1238

# else

1239

# ifndef LACKS_SYS_PARAM_H

1240

# include <sys/param.h>

1241

# endif

1242

# ifdef EXEC_PAGESIZE

1243

# define malloc_getpagesize EXEC_PAGESIZE

1244

# else

1245

# ifdef NBPG

1246

# ifndef CLSIZE

1247

# define malloc_getpagesize NBPG

1248

# else

1249

# define malloc_getpagesize (NBPG * CLSIZE)

1250

# endif

1251

# else

1252

# ifdef NBPC

1253

# define malloc_getpagesize NBPC

1254

# else

1255

# ifdef PAGESIZE

1256

# define malloc_getpagesize PAGESIZE

1257

# else /* just guess */

1258

# define malloc_getpagesize ((size_t)4096U)

1259

# endif

1260

# endif

1261

# endif

1262

# endif

1263

# endif

1264

# endif

1265

# endif

1266

#endif

1267

#endif

1268

1269

/* ------------------- size_t and alignment properties -------------------- */

1270

1271

/* The byte and bit size of a size_t */

1272

#define SIZE_T_SIZE (sizeof(size_t))

1273

#define SIZE_T_BITSIZE (sizeof(size_t) << 3)

1274

1275

/* Some constants coerced to size_t */

1276

/* Annoying but necessary to avoid errors on some plaftorms */

1277

#define SIZE_T_ZERO ((size_t)0)

1278

#define SIZE_T_ONE ((size_t)1)

1279

#define SIZE_T_TWO ((size_t)2)

1280

#define TWO_SIZE_T_SIZES (SIZE_T_SIZE<<1)

1281

#define FOUR_SIZE_T_SIZES (SIZE_T_SIZE<<2)

1282

#define SIX_SIZE_T_SIZES (FOUR_SIZE_T_SIZES+TWO_SIZE_T_SIZES)

1283

#define HALF_MAX_SIZE_T (MAX_SIZE_T / 2U)

1284

1285

/* The bit mask value corresponding to MALLOC_ALIGNMENT */

1286

#define CHUNK_ALIGN_MASK (MALLOC_ALIGNMENT - SIZE_T_ONE)

1287

1288

/* True if address a has acceptable alignment */

1289

#define is_aligned(A) (((size_t)((A)) & (CHUNK_ALIGN_MASK)) == 0)

1290

1291

/* the number of bytes to offset an address to align it */

1292

#define align_offset(A)\

1293

((((size_t)(A) & CHUNK_ALIGN_MASK) == 0)? 0 :\

1294

((MALLOC_ALIGNMENT - ((size_t)(A) & CHUNK_ALIGN_MASK)) & CHUNK_ALIGN_MASK))

1295

1296

/* -------------------------- MMAP preliminaries ------------------------- */

1297

1298

/*

1299

If HAVE_MORECORE or HAVE_MMAP are false, we just define calls and

1300

checks to fail so compiler optimizer can delete code rather than

1301

using so many "#if"s.

1302

*/

1303

1304

1305

/* MORECORE and MMAP must return MFAIL on failure */

1306

#define MFAIL ((void*)(MAX_SIZE_T))

1307

#define CMFAIL ((char*)(MFAIL)) /* defined for convenience */

1308

1309

#if !HAVE_MMAP

1310

#define IS_MMAPPED_BIT (SIZE_T_ZERO)

1311

#define USE_MMAP_BIT (SIZE_T_ZERO)

1312

#define CALL_MMAP(s) MFAIL

1313

#define CALL_MUNMAP(a, s) (-1)

1314

#define DIRECT_MMAP(s) MFAIL

1315

1316

#else /* HAVE_MMAP */

1317

#define IS_MMAPPED_BIT (SIZE_T_ONE)

1318

#define USE_MMAP_BIT (SIZE_T_ONE)

1319

1320

#ifndef WIN32

1321

#define CALL_MUNMAP(a, s) munmap((a), (s))

1322

#define MMAP_PROT (PROT_READ|PROT_WRITE)

1323

#if !defined(MAP_ANONYMOUS) && defined(MAP_ANON)

1324

#define MAP_ANONYMOUS MAP_ANON

1325

#endif /* MAP_ANON */

1326

#ifdef MAP_ANONYMOUS

1327

#define MMAP_FLAGS (MAP_PRIVATE|MAP_ANONYMOUS)

1328

#define CALL_MMAP(s) mmap(0, (s), MMAP_PROT, MMAP_FLAGS, -1, 0)

1329

#else /* MAP_ANONYMOUS */

1330

/*

1331

Nearly all versions of mmap support MAP_ANONYMOUS, so the following

1332

is unlikely to be needed, but is supplied just in case.

1333

*/

1334

#define MMAP_FLAGS (MAP_PRIVATE)

1335

static int dev_zero_fd = -1; /* Cached file descriptor for /dev/zero. */

1336

#define CALL_MMAP(s) ((dev_zero_fd < 0) ? \

1337

(dev_zero_fd = open("/dev/zero", O_RDWR), \

1338

mmap(0, (s), MMAP_PROT, MMAP_FLAGS, dev_zero_fd, 0)) : \

1339

mmap(0, (s), MMAP_PROT, MMAP_FLAGS, dev_zero_fd, 0))

1340

#endif /* MAP_ANONYMOUS */

1341

1342

#define DIRECT_MMAP(s) CALL_MMAP(s)

1343

#else /* WIN32 */

1344

1345

/* Win32 MMAP via VirtualAlloc */

1346

static FORCEINLINE void* win32mmap(size_t size) {

1347

void* ptr = VirtualAlloc(0, size, MEM_RESERVE|MEM_COMMIT, PAGE_READWRITE);

1348

return (ptr != 0)? ptr: MFAIL;

1349

}

1350

1351

/* For direct MMAP, use MEM_TOP_DOWN to minimize interference */

1352

static FORCEINLINE void* win32direct_mmap(size_t size) {

1353

void* ptr = VirtualAlloc(0, size, MEM_RESERVE|MEM_COMMIT|MEM_TOP_DOWN,

1354

PAGE_READWRITE);

1355

return (ptr != 0)? ptr: MFAIL;

1356

}

1357

1358

/* This function supports releasing coalesed segments */

1359

static FORCEINLINE int win32munmap(void* ptr, size_t size) {

1360

MEMORY_BASIC_INFORMATION minfo;

1361

char* cptr = (char *) ptr;

1362

while (size) {

1363

if (VirtualQuery(cptr, &minfo, sizeof(minfo)) == 0)

1364

return -1;

1365

if (minfo.BaseAddress != cptr || minfo.AllocationBase != cptr ||

1366

minfo.State != MEM_COMMIT || minfo.RegionSize > size)

1367

return -1;

1368

if (VirtualFree(cptr, 0, MEM_RELEASE) == 0)

1369

return -1;

1370

cptr += minfo.RegionSize;

1371

size -= minfo.RegionSize;

1372

}

1373

return 0;

1374

}

1375

1376

#define CALL_MMAP(s) win32mmap(s)

1377

#define CALL_MUNMAP(a, s) win32munmap((a), (s))

1378

#define DIRECT_MMAP(s) win32direct_mmap(s)

1379

#endif /* WIN32 */

1380

#endif /* HAVE_MMAP */

1381

1382

#if HAVE_MMAP && HAVE_MREMAP

1383

#define CALL_MREMAP(addr, osz, nsz, mv) mremap((addr), (osz), (nsz), (mv))

1384

#else /* HAVE_MMAP && HAVE_MREMAP */

1385

#define CALL_MREMAP(addr, osz, nsz, mv) ((void)(addr),(void)(osz), \

1386

(void)(nsz), (void)(mv),MFAIL)

1387

#endif /* HAVE_MMAP && HAVE_MREMAP */

1388

1389

#if HAVE_MORECORE

1390

#define CALL_MORECORE(S) MORECORE(S)

1391

#else /* HAVE_MORECORE */

1392

#define CALL_MORECORE(S) MFAIL

1393

#endif /* HAVE_MORECORE */

1394

1395

/* mstate bit set if continguous morecore disabled or failed */

1396

#define USE_NONCONTIGUOUS_BIT (4U)

1397

1398

/* segment bit set in create_mspace_with_base */

1399

#define EXTERN_BIT (8U)

1400

1401

1402

/* --------------------------- Lock preliminaries ------------------------ */

1403

1404

#if USE_LOCKS

1405

1406

#if USE_LOCKS==1

1407

1408

/*

1409

When locks are defined, there are up to two global locks:

1410

1411

* If HAVE_MORECORE, morecore_mutex protects sequences of calls to

1412

MORECORE. In many cases sys_alloc requires two calls, that should

1413

not be interleaved with calls by other threads. This does not

1414

protect against direct calls to MORECORE by other threads not

1415

using this lock, so there is still code to cope the best we can on

1416

interference.

1417

1418

* magic_init_mutex ensures that mparams.magic and other

1419

unique mparams values are initialized only once.

1420

*/

1421

1422

#ifndef WIN32

1423

/* By default use posix locks */

1424

#include <pthread.h>

1425

1426

#if defined(__GNUC__) && (defined(__i386__) || defined(__x86_64__))

1427

/* Go for assembler spin locks on x86 and x64 */

1428

struct pthread_mlock_t

1429

{

1430

volatile pthread_t threadid;

1431

volatile unsigned int c;

1432

volatile unsigned int l;

1433

};

1434

#define MLOCK_T struct pthread_mlock_t

1435

#define CURRENT_THREAD pthread_self()

1436

static FORCEINLINE int pthread_acquire_lock (MLOCK_T *sl) {

1437

if(CURRENT_THREAD==sl->threadid)

1438

++sl->c;

1439

else for (;;) {

1440

int ret;

1441

__asm__ __volatile__ ("pause\n\tlock cmpxchgl %2,(%1)" : "=a" (ret) : "r" (&sl->l), "r" (1), "a" (0));

1442

if(!ret) {

1443

assert(!sl->threadid);

1444

sl->threadid=CURRENT_THREAD;

1445

sl->c=1;

1446

break;

1447

}

1448

sched_yield();

1449

}

1450

1451

return 0;

1452

}

1453

1454

static FORCEINLINE void pthread_release_lock (MLOCK_T *sl) {

1455

int ret;

1456

assert(CURRENT_THREAD==sl->threadid);

1457

if (!--sl->c) {

1458

sl->threadid=0;

1459

__asm__ __volatile__ ("xchgl %2,(%1)" : "=r" (ret) : "r" (&sl->l), "0" (0));

1460

}

1461

}

1462

1463

static FORCEINLINE int pthread_try_lock (MLOCK_T *sl) {

1464

int ret;

1465

__asm__ __volatile__ ("pause\n\tlock cmpxchgl %2,(%1)" : "=a" (ret) : "r" (&sl->l), "r" (1), "a" (0));

1466

if(!ret){

1467

assert(!sl->threadid);

1468

sl->threadid=CURRENT_THREAD;

1469

sl->c=1;

1470

return 1;

1471

}

1472

return 0;

1473

}

1474

1475

#define INITIAL_LOCK(sl) (memset((sl), 0, sizeof(MLOCK_T)), 0)

1476

#define ACQUIRE_LOCK(sl) pthread_acquire_lock(sl)

1477

#define RELEASE_LOCK(sl) pthread_release_lock(sl)

1478

#define TRY_LOCK(sl) pthread_try_lock(sl)

1479

#define IS_LOCKED(sl) ((sl)->l)

1480

1481

#if HAVE_MORECORE

1482

static MLOCK_T morecore_mutex = {0, 0 };

1483

#endif /* HAVE_MORECORE */

1484

1485

static MLOCK_T magic_init_mutex = {0, 0 };

1486

1487

#else

1488

1489

/* The POSIX threads implementation */

1490

struct pthread_mlock_t

1491

{

1492

volatile unsigned int c;

1493

pthread_mutex_t l;

1494

};

1495

#define MLOCK_T struct pthread_mlock_t

1496

#define CURRENT_THREAD pthread_self()

1497

static FORCEINLINE int pthread_acquire_lock (MLOCK_T *sl) {

1498

if(!pthread_mutex_lock(&(sl)->l)){

1499

sl->c++;

1500

return 0;

1501

}

1502

return 1;

1503

}

1504

1505

static FORCEINLINE void pthread_release_lock (MLOCK_T *sl) {

1506

--sl->c;

1507

pthread_mutex_unlock(&(sl)->l);

1508

}

1509

1510

static FORCEINLINE int pthread_try_lock (MLOCK_T *sl) {

1511

if(!pthread_mutex_trylock(&(sl)->l)){

1512

sl->c++;

1513

return 1;

1514

}

1515

return 0;

1516

}

1517

1518

static FORCEINLINE int pthread_init_lock (MLOCK_T *sl) {

1519

pthread_mutexattr_t attr;

1520

sl->c=0;

1521

if(pthread_mutexattr_init(&attr)) return 1;

1522

if(pthread_mutexattr_settype(&attr, PTHREAD_MUTEX_RECURSIVE)) return 1;

1523

if(pthread_mutex_init(&sl->l, &attr)) return 1;

1524

pthread_mutexattr_destroy(&attr);

1525

return 0;

1526

}

1527

1528

static FORCEINLINE int pthread_islocked (MLOCK_T *sl) {

1529

#if 0 /* This will be faster on SMP systems which enforce cache consistency */

1530

return sl->c!=0;

1531

#else

1532

/* Doing this correctly portably means inefficient code :( */

1533

if(!pthread_try_lock(sl)){

1534

int ret=(sl->c!=0);

1535

pthread_mutex_unlock(sl);

1536

return ret;

1537

}

1538

return 0;

1539

#endif

1540

}

1541

1542

1543

#define INITIAL_LOCK(sl) pthread_init_lock(sl)

1544

#define ACQUIRE_LOCK(sl) pthread_acquire_lock(sl)

1545

#define RELEASE_LOCK(sl) pthread_release_lock(sl)

1546

#define TRY_LOCK(sl) pthread_try_lock(sl)

1547

#define IS_LOCKED(sl) pthread_islocked(sl)

1548

1549

#if HAVE_MORECORE

1550

static MLOCK_T morecore_mutex = {0, PTHREAD_MUTEX_INITIALIZER };

1551

#endif /* HAVE_MORECORE */

1552

1553

static MLOCK_T magic_init_mutex = {0, PTHREAD_MUTEX_INITIALIZER };

1554

#endif /* __GNUC__ && i386 */

1555

1556

#else /* WIN32 */

1557

/*

1558

Because lock-protected regions have bounded times, and there

1559

are no recursive lock calls, we can use simple spinlocks.

1560

*/

1561

1562

#if defined(_MSC_VER) && _MSC_VER>=1310

1563

#if 1

1564

#ifndef _M_AMD64

1565

// These are already defined on AMD64 builds

1566

#ifdef __cplusplus

1567

extern "C" {

1568

#endif

1569

LONG __cdecl _InterlockedCompareExchange(LPLONG volatile Dest, LONG Exchange, LONG Comp);

1570

LONG __cdecl _InterlockedExchange(LPLONG volatile Target, LONG Value);

1571

#ifdef __cplusplus

1572

}

1573

#endif

1574

#endif

1575

// MSVC7.1 Intrinsics are far faster than win32 functions

1576

#pragma intrinsic (_InterlockedCompareExchange)

1577

#pragma intrinsic (_InterlockedExchange)

1578

#define interlockedcompareexchange _InterlockedCompareExchange

1579

#define interlockedexchange _InterlockedExchange

1580

#else

1581

#define interlockedcompareexchange InterlockedCompareExchange

1582

#define interlockedexchange InterlockedExchange

1583

#endif

1584

1585

struct win32_mlock_t

1586

{

1587

volatile long threadid;

1588

volatile unsigned int c;

1589

long l;

1590

};

1591

#define MLOCK_T struct win32_mlock_t

1592

#define CURRENT_THREAD GetCurrentThreadId()

1593

static FORCEINLINE int win32_acquire_lock (MLOCK_T *sl) {

1594

long mythreadid=CURRENT_THREAD;

1595

if(mythreadid==sl->threadid)

1596

++sl->c;

1597

else for (;;) {

1598

if (!interlockedexchange(&sl->l, 1)) {

1599

assert(!sl->threadid);

1600

sl->threadid=mythreadid;

1601

sl->c=1;

1602

break;

1603

}

1604

/*YieldProcessor();*/

1605

}

1606

1607

return 0;

1608

}

1609

1610

static FORCEINLINE void win32_release_lock (MLOCK_T *sl) {

1611

assert(CURRENT_THREAD==sl->threadid);

1612

if (!--sl->c) {

1613

sl->threadid=0;

1614

interlockedexchange (&sl->l, 0);

1615

}

1616

}

1617

1618

static FORCEINLINE int win32_try_lock (MLOCK_T *sl) {

1619

if (!interlockedexchange(&sl->l, 1)){

1620

assert(!sl->threadid);

1621

sl->threadid=CURRENT_THREAD;

1622

sl->c=1;

1623

return 1;

1624

}

1625

return 0;

1626

}

1627

1628

1629

#define INITIAL_LOCK(sl) (memset(sl, 0, sizeof(MLOCK_T)), 0)

1630

#define ACQUIRE_LOCK(sl) win32_acquire_lock(sl)

1631

#define RELEASE_LOCK(sl) win32_release_lock(sl)

1632

#define TRY_LOCK(sl) win32_try_lock(sl)

1633

#define IS_LOCKED(sl) ((sl)->l)

1634

#else

1635

/* Critical section implementation */

1636

#define MLOCK_T CRITICAL_SECTION

1637

#define CURRENT_THREAD GetCurrentThreadId()

1638

#define INITIAL_LOCK(s) (!InitializeCriticalSectionAndSpinCount((s), 4000)

1639

#define ACQUIRE_LOCK(s) ( (!((s))->DebugInfo ? INITIAL_LOCK((s)) : 0), !EnterCriticalSection((s)), 0)

1640

#define RELEASE_LOCK(s) ( LeaveCriticalSection((s)), 0 )

1641

#define TRY_LOCK(s) ( TryEnterCriticalSection((s)) )

1642

#define IS_LOCKED(s) ( (s)->LockCount >= 0 )

1643

#define NULL_LOCK_INITIALIZER

1644

1645

#endif /* 1 */

1646

#if HAVE_MORECORE

1647

static MLOCK_T morecore_mutex;

1648

#endif /* HAVE_MORECORE */

1649

static MLOCK_T magic_init_mutex;

1650

#endif /* WIN32 */

1651

1652

#else

1653

/* User defines their own locks */

1654

#if HAVE_MORECORE

1655

static MLOCK_T morecore_mutex NULL_LOCK_INITIALIZER;

1656

#endif /* HAVE_MORECORE */

1657

static MLOCK_T magic_init_mutex NULL_LOCK_INITIALIZER;

1658

1659

#endif /* USE_LOCKS==1 */

1660

1661

#define USE_LOCK_BIT (2U)

1662

#else /* USE_LOCKS */

1663

#define USE_LOCK_BIT (0U)

1664

#define INITIAL_LOCK(l)

1665

#endif /* USE_LOCKS */

1666

1667

#if USE_LOCKS && HAVE_MORECORE

1668

#define ACQUIRE_MORECORE_LOCK() ACQUIRE_LOCK(&morecore_mutex);

1669

#define RELEASE_MORECORE_LOCK() RELEASE_LOCK(&morecore_mutex);

1670

#else /* USE_LOCKS && HAVE_MORECORE */

1671

#define ACQUIRE_MORECORE_LOCK()

1672

#define RELEASE_MORECORE_LOCK()

1673

#endif /* USE_LOCKS && HAVE_MORECORE */

1674

1675

#if USE_LOCKS

1676

#define ACQUIRE_MAGIC_INIT_LOCK() ACQUIRE_LOCK(&magic_init_mutex);

1677

#define RELEASE_MAGIC_INIT_LOCK() RELEASE_LOCK(&magic_init_mutex);

1678

#else /* USE_LOCKS */

1679

#define ACQUIRE_MAGIC_INIT_LOCK()

1680

#define RELEASE_MAGIC_INIT_LOCK()

1681

#endif /* USE_LOCKS */

1682

1683

1684

/* ----------------------- Chunk representations ------------------------ */

1685

1686

/*

1687

(The following includes lightly edited explanations by Colin Plumb.)

1688

1689

The malloc_chunk declaration below is misleading (but accurate and

1690

necessary). It declares a "view" into memory allowing access to

1691

necessary fields at known offsets from a given base.

1692

1693

Chunks of memory are maintained using a `boundary tag' method as

1694

originally described by Knuth. (See the paper by Paul Wilson

1695

ftp://ftp.cs.utexas.edu/pub/garbage/allocsrv.ps for a survey of such

1696

techniques.) Sizes of free chunks are stored both in the front of

1697

each chunk and at the end. This makes consolidating fragmented

1698

chunks into bigger chunks fast. The head fields also hold bits

1699

representing whether chunks are free or in use.

1700

1701

Here are some pictures to make it clearer. They are "exploded" to

1702

show that the state of a chunk can be thought of as extending from

1703

the high 31 bits of the head field of its header through the

1704

prev_foot and PINUSE_BIT bit of the following chunk header.

1705

1706

A chunk that's in use looks like:

1707

1708

chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

1709

| Size of previous chunk (if P = 1) |

1710

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

1711

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |P|

1712

| Size of this chunk 1| +-+

1713

mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

1714

| |

1715

+- -+

1716

| |

1717

+- -+

1718

| :

1719

+- size - sizeof(size_t) available payload bytes -+

1720

: |

1721

chunk-> +- -+

1722

| |

1723

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

1724

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |1|

1725

| Size of next chunk (may or may not be in use) | +-+

1726

mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

1727

1728

And if it's free, it looks like this:

1729

1730

chunk-> +- -+

1731

| User payload (must be in use, or we would have merged!) |

1732

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

1733

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |P|

1734

| Size of this chunk 0| +-+

1735

mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

1736

| Next pointer |

1737

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

1738

| Prev pointer |

1739

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

1740

| :

1741

+- size - sizeof(struct chunk) unused bytes -+

1742

: |

1743

chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

1744

| Size of this chunk |

1745

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

1746

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |0|

1747

| Size of next chunk (must be in use, or we would have merged)| +-+

1748

mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

1749

| :

1750

+- User payload -+

1751

: |

1752

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

1753

|0|

1754

+-+

1755

Note that since we always merge adjacent free chunks, the chunks

1756

adjacent to a free chunk must be in use.

1757

1758

Given a pointer to a chunk (which can be derived trivially from the

1759

payload pointer) we can, in O(1) time, find out whether the adjacent

1760

chunks are free, and if so, unlink them from the lists that they

1761

are on and merge them with the current chunk.

1762

1763

Chunks always begin on even word boundaries, so the mem portion

1764

(which is returned to the user) is also on an even word boundary, and

1765

thus at least double-word aligned.

1766

1767

The P (PINUSE_BIT) bit, stored in the unused low-order bit of the

1768

chunk size (which is always a multiple of two words), is an in-use

1769

bit for the *previous* chunk. If that bit is *clear*, then the

1770

word before the current chunk size contains the previous chunk

1771

size, and can be used to find the front of the previous chunk.

1772

The very first chunk allocated always has this bit set, preventing

1773

access to non-existent (or non-owned) memory. If pinuse is set for

1774

any given chunk, then you CANNOT determine the size of the

1775

previous chunk, and might even get a memory addressing fault when

1776

trying to do so.

1777

1778

The C (CINUSE_BIT) bit, stored in the unused second-lowest bit of

1779

the chunk size redundantly records whether the current chunk is

1780

inuse. This redundancy enables usage checks within free and realloc,

1781

and reduces indirection when freeing and consolidating chunks.

1782

1783

Each freshly allocated chunk must have both cinuse and pinuse set.

1784

That is, each allocated chunk borders either a previously allocated

1785

and still in-use chunk, or the base of its memory arena. This is

1786

ensured by making all allocations from the the `lowest' part of any

1787

found chunk. Further, no free chunk physically borders another one,

1788

so each free chunk is known to be preceded and followed by either

1789

inuse chunks or the ends of memory.

1790

1791

Note that the `foot' of the current chunk is actually represented

1792

as the prev_foot of the NEXT chunk. This makes it easier to

1793

deal with alignments etc but can be very confusing when trying

1794

to extend or adapt this code.

1795

1796

The exceptions to all this are

1797

1798

1. The special chunk `top' is the top-most available chunk (i.e.,

1799

the one bordering the end of available memory). It is treated

1800

specially. Top is never included in any bin, is used only if

1801

no other chunk is available, and is released back to the

1802

system if it is very large (see M_TRIM_THRESHOLD). In effect,

1803

the top chunk is treated as larger (and thus less well

1804

fitting) than any other available chunk. The top chunk

1805

doesn't update its trailing size field since there is no next

1806

contiguous chunk that would have to index off it. However,

1807

space is still allocated for it (TOP_FOOT_SIZE) to enable

1808

separation or merging when space is extended.

1809

1810

3. Chunks allocated via mmap, which have the lowest-order bit

1811

(IS_MMAPPED_BIT) set in their prev_foot fields, and do not set

1812

PINUSE_BIT in their head fields. Because they are allocated

1813

one-by-one, each must carry its own prev_foot field, which is

1814

also used to hold the offset this chunk has within its mmapped

1815

region, which is needed to preserve alignment. Each mmapped

1816

chunk is trailed by the first two fields of a fake next-chunk

1817

for sake of usage checks.

1818

1819

*/

1820

1821

struct malloc_chunk {

1822

size_t prev_foot; /* Size of previous chunk (if free). */

1823

size_t head; /* Size and inuse bits. */

1824

struct malloc_chunk* fd; /* double links -- used only if free. */

1825

struct malloc_chunk* bk;

1826

};

1827

1828

typedef struct malloc_chunk mchunk;

1829

typedef struct malloc_chunk* mchunkptr;

1830

typedef struct malloc_chunk* sbinptr; /* The type of bins of chunks */

1831

typedef unsigned int bindex_t; /* Described below */

1832

typedef unsigned int binmap_t; /* Described below */

1833

typedef unsigned int flag_t; /* The type of various bit flag sets */

1834

1835

/* ------------------- Chunks sizes and alignments ----------------------- */

1836

1837

#define MCHUNK_SIZE (sizeof(mchunk))

1838

1839

#if FOOTERS

1840

#define CHUNK_OVERHEAD (TWO_SIZE_T_SIZES)

1841

#else /* FOOTERS */

1842

#define CHUNK_OVERHEAD (SIZE_T_SIZE)

1843

#endif /* FOOTERS */

1844

1845

/* MMapped chunks need a second word of overhead ... */

1846

#define MMAP_CHUNK_OVERHEAD (TWO_SIZE_T_SIZES)

1847

/* ... and additional padding for fake next-chunk at foot */

1848

#define MMAP_FOOT_PAD (FOUR_SIZE_T_SIZES)

1849

1850

/* The smallest size we can malloc is an aligned minimal chunk */

1851

#define MIN_CHUNK_SIZE\

1852

((MCHUNK_SIZE + CHUNK_ALIGN_MASK) & ~CHUNK_ALIGN_MASK)

1853

1854

/* conversion from malloc headers to user pointers, and back */

1855

#define chunk2mem(p) ((void*)((char*)(p) + TWO_SIZE_T_SIZES))

1856

#define mem2chunk(mem) ((mchunkptr)((char*)(mem) - TWO_SIZE_T_SIZES))

1857

/* chunk associated with aligned address A */

1858

#define align_as_chunk(A) (mchunkptr)((A) + align_offset(chunk2mem(A)))

1859

1860

/* Bounds on request (not chunk) sizes. */

1861

#define MAX_REQUEST ((-MIN_CHUNK_SIZE) << 2)

1862

#define MIN_REQUEST (MIN_CHUNK_SIZE - CHUNK_OVERHEAD - SIZE_T_ONE)

1863

1864

/* pad request bytes into a usable size */

1865

#define pad_request(req) \

1866

(((req) + CHUNK_OVERHEAD + CHUNK_ALIGN_MASK) & ~CHUNK_ALIGN_MASK)

1867

1868

/* pad request, checking for minimum (but not maximum) */

1869

#define request2size(req) \

1870

(((req) < MIN_REQUEST)? MIN_CHUNK_SIZE : pad_request(req))

1871

1872

1873

/* ------------------ Operations on head and foot fields ----------------- */

1874

1875

/*

1876

The head field of a chunk is or'ed with PINUSE_BIT when previous

1877

adjacent chunk in use, and or'ed with CINUSE_BIT if this chunk is in

1878

use. If the chunk was obtained with mmap, the prev_foot field has

1879

IS_MMAPPED_BIT set, otherwise holding the offset of the base of the

1880

mmapped region to the base of the chunk.

1881

*/

1882

1883

#define PINUSE_BIT (SIZE_T_ONE)

1884

#define CINUSE_BIT (SIZE_T_TWO)

1885

#define INUSE_BITS (PINUSE_BIT|CINUSE_BIT)

1886

1887

/* Head value for fenceposts */

1888

#define FENCEPOST_HEAD (INUSE_BITS|SIZE_T_SIZE)

1889

1890

/* extraction of fields from head words */

1891

#define cinuse(p) ((p)->head & CINUSE_BIT)

1892

#define pinuse(p) ((p)->head & PINUSE_BIT)

1893

#define chunksize(p) ((p)->head & ~(INUSE_BITS))

1894

1895

#define clear_pinuse(p) ((p)->head &= ~PINUSE_BIT)

1896

#define clear_cinuse(p) ((p)->head &= ~CINUSE_BIT)

1897

1898

/* Treat space at ptr +/- offset as a chunk */

1899

#define chunk_plus_offset(p, s) ((mchunkptr)(((char*)(p)) + (s)))

1900

#define chunk_minus_offset(p, s) ((mchunkptr)(((char*)(p)) - (s)))

1901

1902

/* Ptr to next or previous physical malloc_chunk. */

1903

#define next_chunk(p) ((mchunkptr)( ((char*)(p)) + ((p)->head & ~INUSE_BITS)))

1904

#define prev_chunk(p) ((mchunkptr)( ((char*)(p)) - ((p)->prev_foot) ))

1905

1906

/* extract next chunk's pinuse bit */

1907

#define next_pinuse(p) ((next_chunk(p)->head) & PINUSE_BIT)

1908

1909

/* Get/set size at footer */

1910

#define get_foot(p, s) (((mchunkptr)((char*)(p) + (s)))->prev_foot)

1911

#define set_foot(p, s) (((mchunkptr)((char*)(p) + (s)))->prev_foot = (s))

1912

1913

/* Set size, pinuse bit, and foot */

1914

#define set_size_and_pinuse_of_free_chunk(p, s)\

1915

((p)->head = (s|PINUSE_BIT), set_foot(p, s))

1916

1917

/* Set size, pinuse bit, foot, and clear next pinuse */

1918

#define set_free_with_pinuse(p, s, n)\

1919

(clear_pinuse(n), set_size_and_pinuse_of_free_chunk(p, s))

1920

1921

#define is_mmapped(p)\

1922

(!((p)->head & PINUSE_BIT) && ((p)->prev_foot & IS_MMAPPED_BIT))

1923

1924

/* Get the internal overhead associated with chunk p */

1925

#define overhead_for(p)\

1926

(is_mmapped(p)? MMAP_CHUNK_OVERHEAD : CHUNK_OVERHEAD)

1927

1928

/* Return true if malloced space is not necessarily cleared */

1929

#if MMAP_CLEARS

1930

#define calloc_must_clear(p) (!is_mmapped(p))

1931

#else /* MMAP_CLEARS */

1932

#define calloc_must_clear(p) (1)

1933

#endif /* MMAP_CLEARS */

1934

1935

/* ---------------------- Overlaid data structures ----------------------- */

1936

1937

/*

1938

When chunks are not in use, they are treated as nodes of either

1939

lists or trees.

1940

1941

"Small" chunks are stored in circular doubly-linked lists, and look

1942

like this:

1943

1944

chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

1945

| Size of previous chunk |

1946

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

1947

`head:' | Size of chunk, in bytes |P|

1948

mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

1949

| Forward pointer to next chunk in list |

1950

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

1951

| Back pointer to previous chunk in list |

1952

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

1953

| Unused space (may be 0 bytes long) .

1954

. .

1955

. |

1956

nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

1957

`foot:' | Size of chunk, in bytes |

1958

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

1959

1960

Larger chunks are kept in a form of bitwise digital trees (aka

1961

tries) keyed on chunksizes. Because malloc_tree_chunks are only for

1962

free chunks greater than 256 bytes, their size doesn't impose any

1963

constraints on user chunk sizes. Each node looks like:

1964

1965

chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

1966

| Size of previous chunk |

1967

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

1968

`head:' | Size of chunk, in bytes |P|

1969

mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

1970

| Forward pointer to next chunk of same size |

1971

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

1972

| Back pointer to previous chunk of same size |

1973

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

1974

| Pointer to left child (child[0]) |

1975

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

1976

| Pointer to right child (child[1]) |

1977

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

1978

| Pointer to parent |

1979

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

1980

| bin index of this chunk |

1981

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

1982

| Unused space .

1983

. |

1984

nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

1985

`foot:' | Size of chunk, in bytes |

1986

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

1987

1988

Each tree holding treenodes is a tree of unique chunk sizes. Chunks

1989

of the same size are arranged in a circularly-linked list, with only

1990

the oldest chunk (the next to be used, in our FIFO ordering)

1991

actually in the tree. (Tree members are distinguished by a non-null

1992

parent pointer.) If a chunk with the same size an an existing node

1993

is inserted, it is linked off the existing node using pointers that

1994

work in the same way as fd/bk pointers of small chunks.

1995

1996

Each tree contains a power of 2 sized range of chunk sizes (the

1997

smallest is 0x100 <= x < 0x180), which is is divided in half at each

1998

tree level, with the chunks in the smaller half of the range (0x100

1999

<= x < 0x140 for the top nose) in the left subtree and the larger

2000

half (0x140 <= x < 0x180) in the right subtree. This is, of course,

2001

done by inspecting individual bits.

2002

2003

Using these rules, each node's left subtree contains all smaller

2004

sizes than its right subtree. However, the node at the root of each

2005

subtree has no particular ordering relationship to either. (The

2006

dividing line between the subtree sizes is based on trie relation.)

2007

If we remove the last chunk of a given size from the interior of the

2008

tree, we need to replace it with a leaf node. The tree ordering

2009

rules permit a node to be replaced by any leaf below it.

2010

2011

The smallest chunk in a tree (a common operation in a best-fit

2012

allocator) can be found by walking a path to the leftmost leaf in

2013

the tree. Unlike a usual binary tree, where we follow left child

2014

pointers until we reach a null, here we follow the right child

2015

pointer any time the left one is null, until we reach a leaf with

2016

both child pointers null. The smallest chunk in the tree will be

2017

somewhere along that path.

2018

2019

The worst case number of steps to add, find, or remove a node is

2020

bounded by the number of bits differentiating chunks within

2021

bins. Under current bin calculations, this ranges from 6 up to 21

2022

(for 32 bit sizes) or up to 53 (for 64 bit sizes). The typical case

2023

is of course much better.

2024

*/

2025

2026

struct malloc_tree_chunk {

2027

/* The first four fields must be compatible with malloc_chunk */

2028

size_t prev_foot;

2029

size_t head;

2030

struct malloc_tree_chunk* fd;

2031

struct malloc_tree_chunk* bk;

2032

2033

struct malloc_tree_chunk* child[2];

2034

struct malloc_tree_chunk* parent;

2035

bindex_t index;

2036

};

2037

2038

typedef struct malloc_tree_chunk tchunk;

2039

typedef struct malloc_tree_chunk* tchunkptr;

2040

typedef struct malloc_tree_chunk* tbinptr; /* The type of bins of trees */

2041

2042

/* A little helper macro for trees */

2043

#define leftmost_child(t) ((t)->child[0] != 0? (t)->child[0] : (t)->child[1])

2044

2045

/* ----------------------------- Segments -------------------------------- */

2046

2047

/*

2048

Each malloc space may include non-contiguous segments, held in a

2049

list headed by an embedded malloc_segment record representing the

2050

top-most space. Segments also include flags holding properties of

2051

the space. Large chunks that are directly allocated by mmap are not

2052

included in this list. They are instead independently created and

2053

destroyed without otherwise keeping track of them.

2054

2055

Segment management mainly comes into play for spaces allocated by

2056

MMAP. Any call to MMAP might or might not return memory that is

2057

adjacent to an existing segment. MORECORE normally contiguously

2058

extends the current space, so this space is almost always adjacent,

2059

which is simpler and faster to deal with. (This is why MORECORE is

2060

used preferentially to MMAP when both are available -- see

2061

sys_alloc.) When allocating using MMAP, we don't use any of the

2062

hinting mechanisms (inconsistently) supported in various

2063

implementations of unix mmap, or distinguish reserving from

2064

committing memory. Instead, we just ask for space, and exploit

2065

contiguity when we get it. It is probably possible to do

2066

better than this on some systems, but no general scheme seems

2067

to be significantly better.

2068

2069

Management entails a simpler variant of the consolidation scheme

2070

used for chunks to reduce fragmentation -- new adjacent memory is

2071

normally prepended or appended to an existing segment. However,

2072

there are limitations compared to chunk consolidation that mostly

2073

reflect the fact that segment processing is relatively infrequent

2074

(occurring only when getting memory from system) and that we

2075

don't expect to have huge numbers of segments:

2076

2077

* Segments are not indexed, so traversal requires linear scans. (It

2078

would be possible to index these, but is not worth the extra

2079

overhead and complexity for most programs on most platforms.)

2080

* New segments are only appended to old ones when holding top-most

2081

memory; if they cannot be prepended to others, they are held in

2082

different segments.

2083

2084

Except for the top-most segment of an mstate, each segment record

2085

is kept at the tail of its segment. Segments are added by pushing

2086

segment records onto the list headed by &mstate.seg for the

2087

containing mstate.

2088

2089

Segment flags control allocation/merge/deallocation policies:

2090

* If EXTERN_BIT set, then we did not allocate this segment,

2091

and so should not try to deallocate or merge with others.

2092

(This currently holds only for the initial segment passed

2093

into create_mspace_with_base.)

2094

* If IS_MMAPPED_BIT set, the segment may be merged with

2095

other surrounding mmapped segments and trimmed/de-allocated

2096

using munmap.

2097

* If neither bit is set, then the segment was obtained using

2098

MORECORE so can be merged with surrounding MORECORE'd segments

2099

and deallocated/trimmed using MORECORE with negative arguments.

2100

*/

2101

2102

struct malloc_segment {

2103

char* base; /* base address */

2104

size_t size; /* allocated size */

2105

struct malloc_segment* next; /* ptr to next segment */

2106

flag_t sflags; /* mmap and extern flag */

2107

};

2108

2109

#define is_mmapped_segment(S) ((S)->sflags & IS_MMAPPED_BIT)

2110

#define is_extern_segment(S) ((S)->sflags & EXTERN_BIT)

2111

2112

typedef struct malloc_segment msegment;

2113

typedef struct malloc_segment* msegmentptr;

2114

2115

/* ---------------------------- malloc_state ----------------------------- */

2116

2117

/*

2118

A malloc_state holds all of the bookkeeping for a space.

2119

The main fields are:

2120

2121

Top

2122

The topmost chunk of the currently active segment. Its size is

2123

cached in topsize. The actual size of topmost space is

2124

topsize+TOP_FOOT_SIZE, which includes space reserved for adding

2125

fenceposts and segment records if necessary when getting more

2126

space from the system. The size at which to autotrim top is

2127

cached from mparams in trim_check, except that it is disabled if

2128

an autotrim fails.

2129

2130

Designated victim (dv)

2131

This is the preferred chunk for servicing small requests that

2132

don't have exact fits. It is normally the chunk split off most

2133

recently to service another small request. Its size is cached in

2134

dvsize. The link fields of this chunk are not maintained since it

2135

is not kept in a bin.

2136

2137

SmallBins

2138

An array of bin headers for free chunks. These bins hold chunks

2139

with sizes less than MIN_LARGE_SIZE bytes. Each bin contains

2140

chunks of all the same size, spaced 8 bytes apart. To simplify

2141

use in double-linked lists, each bin header acts as a malloc_chunk

2142

pointing to the real first node, if it exists (else pointing to

2143

itself). This avoids special-casing for headers. But to avoid

2144

waste, we allocate only the fd/bk pointers of bins, and then use

2145

repositioning tricks to treat these as the fields of a chunk.

2146

2147

TreeBins

2148

Treebins are pointers to the roots of trees holding a range of

2149

sizes. There are 2 equally spaced treebins for each power of two

2150

from TREE_SHIFT to TREE_SHIFT+16. The last bin holds anything

2151

larger.

2152

2153

Bin maps

2154

There is one bit map for small bins ("smallmap") and one for

2155

treebins ("treemap). Each bin sets its bit when non-empty, and

2156

clears the bit when empty. Bit operations are then used to avoid

2157

bin-by-bin searching -- nearly all "search" is done without ever

2158

looking at bins that won't be selected. The bit maps

2159

conservatively use 32 bits per map word, even if on 64bit system.

2160

For a good description of some of the bit-based techniques used

2161

here, see Henry S. Warren Jr's book "Hacker's Delight" (and

2162

supplement at http://hackersdelight.org/). Many of these are

2163

intended to reduce the branchiness of paths through malloc etc, as

2164

well as to reduce the number of memory locations read or written.

2165

2166

Segments

2167

A list of segments headed by an embedded malloc_segment record

2168

representing the initial space.

2169

2170

Address check support

2171

The least_addr field is the least address ever obtained from

2172

MORECORE or MMAP. Attempted frees and reallocs of any address less

2173

than this are trapped (unless INSECURE is defined).

2174

2175

Magic tag

2176

A cross-check field that should always hold same value as mparams.magic.

2177

2178

Flags

2179

Bits recording whether to use MMAP, locks, or contiguous MORECORE

2180

2181

Statistics

2182

Each space keeps track of current and maximum system memory

2183

obtained via MORECORE or MMAP.

2184

2185

Locking

2186

If USE_LOCKS is defined, the "mutex" lock is acquired and released

2187

around every public call using this mspace.

2188

*/

2189

2190

/* Bin types, widths and sizes */

2191

#define NSMALLBINS (32U)

2192

#define NTREEBINS (32U)

2193

#define SMALLBIN_SHIFT (3U)

2194

#define SMALLBIN_WIDTH (SIZE_T_ONE << SMALLBIN_SHIFT)

2195

#define TREEBIN_SHIFT (8U)

2196

#define MIN_LARGE_SIZE (SIZE_T_ONE << TREEBIN_SHIFT)

2197

#define MAX_SMALL_SIZE (MIN_LARGE_SIZE - SIZE_T_ONE)

2198

#define MAX_SMALL_REQUEST (MAX_SMALL_SIZE - CHUNK_ALIGN_MASK - CHUNK_OVERHEAD)

2199

2200

struct malloc_state {

2201

binmap_t smallmap;

2202

binmap_t treemap;

2203

size_t dvsize;

2204

size_t topsize;

2205

char* least_addr;

2206

mchunkptr dv;

2207

mchunkptr top;

2208

size_t trim_check;

2209

size_t magic;

2210

mchunkptr smallbins[(NSMALLBINS+1)*2];

2211

tbinptr treebins[NTREEBINS];

2212

size_t footprint;

2213

size_t max_footprint;

2214

flag_t mflags;

2215

char cachesync[128];

2216

#if USE_LOCKS

2217

MLOCK_T mutex; /* locate lock among fields that rarely change */

2218

#endif /* USE_LOCKS */

2219

msegment seg;

2220

void* nedpool; /* Points back to nedpool owning this mstate */

2221

};

2222

2223

typedef struct malloc_state* mstate;

2224

2225

/* ------------- Global malloc_state and malloc_params ------------------- */

2226

2227

/*

2228

malloc_params holds global properties, including those that can be

2229

dynamically set using mallopt. There is a single instance, mparams,

2230

initialized in init_mparams.

2231

*/

2232

2233

struct malloc_params {

2234

size_t magic;

2235

size_t page_size;

2236

size_t granularity;

2237

size_t mmap_threshold;

2238

size_t trim_threshold;

2239

flag_t default_mflags;

2240

};

2241

2242

static struct malloc_params mparams;

2243

2244

/* The global malloc_state used for all non-"mspace" calls */

2245

static struct malloc_state _gm_;

2246

#define gm (&_gm_)

2247

#define is_global(M) ((M) == &_gm_)

2248

#define is_initialized(M) ((M)->top != 0)

2249

2250

/* -------------------------- system alloc setup ------------------------- */

2251

2252

/* Operations on mflags */

2253

2254

#define use_lock(M) ((M)->mflags & USE_LOCK_BIT)

2255

#define enable_lock(M) ((M)->mflags |= USE_LOCK_BIT)

2256

#define disable_lock(M) ((M)->mflags &= ~USE_LOCK_BIT)

2257

2258

#define use_mmap(M) ((M)->mflags & USE_MMAP_BIT)

2259

#define enable_mmap(M) ((M)->mflags |= USE_MMAP_BIT)

2260

#define disable_mmap(M) ((M)->mflags &= ~USE_MMAP_BIT)

2261

2262

#define use_noncontiguous(M) ((M)->mflags & USE_NONCONTIGUOUS_BIT)

2263

#define disable_contiguous(M) ((M)->mflags |= USE_NONCONTIGUOUS_BIT)

2264

2265

#define set_lock(M,L)\

2266

((M)->mflags = (L)?\

2267

((M)->mflags | USE_LOCK_BIT) :\

2268

((M)->mflags & ~USE_LOCK_BIT))

2269

2270

/* page-align a size */

2271

#define page_align(S)\

2272

(((S) + (mparams.page_size)) & ~(mparams.page_size - SIZE_T_ONE))

2273

2274

/* granularity-align a size */

2275

#define granularity_align(S)\

2276

(((S) + (mparams.granularity)) & ~(mparams.granularity - SIZE_T_ONE))

2277

2278

#define is_page_aligned(S)\

2279

(((size_t)(S) & (mparams.page_size - SIZE_T_ONE)) == 0)

2280

#define is_granularity_aligned(S)\

2281

(((size_t)(S) & (mparams.granularity - SIZE_T_ONE)) == 0)

2282

2283

/* True if segment S holds address A */

2284

#define segment_holds(S, A)\

2285

((char*)(A) >= S->base && (char*)(A) < S->base + S->size)

2286

2287

/* Return segment holding given address */

2288

static msegmentptr segment_holding(mstate m, char* addr) {

2289

msegmentptr sp = &m->seg;

2290

for (;;) {

2291

if (addr >= sp->base && addr < sp->base + sp->size)

2292

return sp;

2293

if ((sp = sp->next) == 0)

2294

return 0;

2295

}

2296

}

2297

2298

/* Return true if segment contains a segment link */

2299

static int has_segment_link(mstate m, msegmentptr ss) {

2300

msegmentptr sp = &m->seg;

2301

for (;;) {

2302

if ((char*)sp >= ss->base && (char*)sp < ss->base + ss->size)

2303

return 1;

2304

if ((sp = sp->next) == 0)

2305

return 0;

2306

}

2307

}

2308

2309

#ifndef MORECORE_CANNOT_TRIM

2310

#define should_trim(M,s) ((s) > (M)->trim_check)

2311

#else /* MORECORE_CANNOT_TRIM */

2312

#define should_trim(M,s) (0)

2313

#endif /* MORECORE_CANNOT_TRIM */

2314

2315

/*

2316

TOP_FOOT_SIZE is padding at the end of a segment, including space

2317

that may be needed to place segment records and fenceposts when new

2318

noncontiguous segments are added.

2319

*/

2320

#define TOP_FOOT_SIZE\

2321

(align_offset(chunk2mem(0))+pad_request(sizeof(struct malloc_segment))+MIN_CHUNK_SIZE)

2322

2323

2324

/* ------------------------------- Hooks -------------------------------- */

2325

2326

/*

2327

PREACTION should be defined to return 0 on success, and nonzero on

2328

failure. If you are not using locking, you can redefine these to do

2329

anything you like.

2330

*/

2331

2332

#if USE_LOCKS

2333

2334

/* Ensure locks are initialized */

2335

#define GLOBALLY_INITIALIZE() (mparams.page_size == 0 && init_mparams())

2336

2337

#define PREACTION(M) ((GLOBALLY_INITIALIZE() || use_lock(M))? ACQUIRE_LOCK(&(M)->mutex) : 0)

2338

#define POSTACTION(M) { if (use_lock(M)) RELEASE_LOCK(&(M)->mutex); }

2339

#else /* USE_LOCKS */

2340

2341

#ifndef PREACTION

2342

#define PREACTION(M) (0)

2343

#endif /* PREACTION */

2344

2345

#ifndef POSTACTION

2346

#define POSTACTION(M)

2347

#endif /* POSTACTION */

2348

2349

#endif /* USE_LOCKS */

2350

2351

/*

2352

CORRUPTION_ERROR_ACTION is triggered upon detected bad addresses.

2353

USAGE_ERROR_ACTION is triggered on detected bad frees and

2354

reallocs. The argument p is an address that might have triggered the

2355

fault. It is ignored by the two predefined actions, but might be

2356

useful in custom actions that try to help diagnose errors.

2357

*/

2358

2359

#if PROCEED_ON_ERROR

2360

2361

/* A count of the number of corruption errors causing resets */

2362

int malloc_corruption_error_count;

2363

2364

/* default corruption action */

2365

static void reset_on_error(mstate m);

2366

2367

#define CORRUPTION_ERROR_ACTION(m) reset_on_error(m)

2368

#define USAGE_ERROR_ACTION(m, p)

2369

2370

#else /* PROCEED_ON_ERROR */

2371

2372

#ifndef CORRUPTION_ERROR_ACTION

2373

#define CORRUPTION_ERROR_ACTION(m) ABORT

2374

#endif /* CORRUPTION_ERROR_ACTION */

2375

2376

#ifndef USAGE_ERROR_ACTION

2377

#define USAGE_ERROR_ACTION(m,p) ABORT

2378

#endif /* USAGE_ERROR_ACTION */

2379

2380

#endif /* PROCEED_ON_ERROR */

2381

2382

/* -------------------------- Debugging setup ---------------------------- */

2383

2384

#if ! DEBUG

2385

2386

#define check_free_chunk(M,P)

2387

#define check_inuse_chunk(M,P)

2388

#define check_malloced_chunk(M,P,N)

2389

#define check_mmapped_chunk(M,P)

2390

#define check_malloc_state(M)

2391

#define check_top_chunk(M,P)

2392

2393

#else /* DEBUG */

2394

#define check_free_chunk(M,P) do_check_free_chunk(M,P)

2395

#define check_inuse_chunk(M,P) do_check_inuse_chunk(M,P)

2396

#define check_top_chunk(M,P) do_check_top_chunk(M,P)

2397

#define check_malloced_chunk(M,P,N) do_check_malloced_chunk(M,P,N)

2398

#define check_mmapped_chunk(M,P) do_check_mmapped_chunk(M,P)

2399

#define check_malloc_state(M) do_check_malloc_state(M)

2400

2401

static void do_check_any_chunk(mstate m, mchunkptr p);

2402

static void do_check_top_chunk(mstate m, mchunkptr p);

2403

static void do_check_mmapped_chunk(mstate m, mchunkptr p);

2404

static void do_check_inuse_chunk(mstate m, mchunkptr p);

2405

static void do_check_free_chunk(mstate m, mchunkptr p);

2406

static void do_check_malloced_chunk(mstate m, void* mem, size_t s);

2407

static void do_check_tree(mstate m, tchunkptr t);

2408

static void do_check_treebin(mstate m, bindex_t i);

2409

static void do_check_smallbin(mstate m, bindex_t i);

2410

static void do_check_malloc_state(mstate m);

2411

static int bin_find(mstate m, mchunkptr x);

2412

static size_t traverse_and_check(mstate m);

2413

#endif /* DEBUG */

2414

2415

/* ---------------------------- Indexing Bins ---------------------------- */

2416

2417

#define is_small(s) (((s) >> SMALLBIN_SHIFT) < NSMALLBINS)

2418

#define small_index(s) ((s) >> SMALLBIN_SHIFT)

2419

#define small_index2size(i) ((i) << SMALLBIN_SHIFT)

2420

#define MIN_SMALL_INDEX (small_index(MIN_CHUNK_SIZE))

2421

2422

/* addressing by index. See above about smallbin repositioning */

2423

#define smallbin_at(M, i) ((sbinptr)((char*)&((M)->smallbins[(i)<<1])))

2424

#define treebin_at(M,i) (&((M)->treebins[i]))

2425

2426

/* assign tree index for size S to variable I */

2427

#if defined(__GNUC__) && (defined(__i386__) || defined(__x86_64__))

2428

#define compute_tree_index(S, I)\

2429

{\

2430

unsigned int X = S >> TREEBIN_SHIFT;\

2431

if (X == 0)\

2432

I = 0;\

2433

else if (X > 0xFFFF)\

2434

I = NTREEBINS-1;\

2435

else {\

2436

unsigned int K;\

2437

__asm__("bsrl\t%1, %0\n\t" : "=r" (K) : "g" (X));\

2438

I = (bindex_t)((K << 1) + ((S >> (K + (TREEBIN_SHIFT-1)) & 1)));\

2439

}\

2440

}

2441

#elif defined(_MSC_VER) && _MSC_VER>=1300

2442

#ifndef BitScanForward /* Try to avoid pulling in WinNT.h */

2443

#ifdef __cplusplus

2444

extern "C" {

2445

#endif

2446

unsigned char _BitScanForward(unsigned long *index, unsigned long mask);

2447

unsigned char _BitScanReverse(unsigned long *index, unsigned long mask);

2448

#ifdef __cplusplus

2449

}

2450

#endif

2451

#define BitScanForward _BitScanForward

2452

#define BitScanReverse _BitScanReverse

2453

#pragma intrinsic(_BitScanForward)

2454

#pragma intrinsic(_BitScanReverse)

2455

#endif

2456

#define compute_tree_index(S, I)\

2457

{\

2458

size_t X = S >> TREEBIN_SHIFT;\

2459

if (X == 0)\

2460

I = 0;\

2461

else if (X > 0xFFFF)\

2462

I = NTREEBINS-1;\

2463

else {\

2464

unsigned int K;\

2465

_BitScanReverse((DWORD *) &K, X);\

2466

I = (bindex_t)((K << 1) + ((S >> (K + (TREEBIN_SHIFT-1)) & 1)));\

2467

}\

2468

}

2469

#else /* GNUC */

2470

#define compute_tree_index(S, I)\

2471

{\

2472

size_t X = S >> TREEBIN_SHIFT;\

2473

if (X == 0)\

2474

I = 0;\

2475

else if (X > 0xFFFF)\

2476

I = NTREEBINS-1;\

2477

else {\

2478

unsigned int Y = (unsigned int)X;\

2479

unsigned int N = ((Y - 0x100) >> 16) & 8;\

2480

unsigned int K = (((Y <<= N) - 0x1000) >> 16) & 4;\

2481

N += K;\

2482

N += K = (((Y <<= K) - 0x4000) >> 16) & 2;\

2483

K = 14 - N + ((Y <<= K) >> 15);\

2484

I = (K << 1) + ((S >> (K + (TREEBIN_SHIFT-1)) & 1));\

2485

}\

2486

}

2487

#endif /* GNUC */

2488

2489

/* Bit representing maximum resolved size in a treebin at i */

2490

#define bit_for_tree_index(i) \

2491

(i == NTREEBINS-1)? (SIZE_T_BITSIZE-1) : (((i) >> 1) + TREEBIN_SHIFT - 2)

2492

2493

/* Shift placing maximum resolved bit in a treebin at i as sign bit */

2494

#define leftshift_for_tree_index(i) \

2495

((i == NTREEBINS-1)? 0 : \

2496

((SIZE_T_BITSIZE-SIZE_T_ONE) - (((i) >> 1) + TREEBIN_SHIFT - 2)))

2497

2498

/* The size of the smallest chunk held in bin with index i */

2499

#define minsize_for_tree_index(i) \

2500

((SIZE_T_ONE << (((i) >> 1) + TREEBIN_SHIFT)) | \

2501

(((size_t)((i) & SIZE_T_ONE)) << (((i) >> 1) + TREEBIN_SHIFT - 1)))

2502

2503

2504

/* ------------------------ Operations on bin maps ----------------------- */

2505

2506

/* bit corresponding to given index */

2507

#define idx2bit(i) ((binmap_t)(1) << (i))

2508

2509

/* Mark/Clear bits with given index */

2510

#define mark_smallmap(M,i) ((M)->smallmap |= idx2bit(i))

2511

#define clear_smallmap(M,i) ((M)->smallmap &= ~idx2bit(i))

2512

#define smallmap_is_marked(M,i) ((M)->smallmap & idx2bit(i))

2513

2514

#define mark_treemap(M,i) ((M)->treemap |= idx2bit(i))

2515

#define clear_treemap(M,i) ((M)->treemap &= ~idx2bit(i))

2516

#define treemap_is_marked(M,i) ((M)->treemap & idx2bit(i))

2517

2518

/* index corresponding to given bit */

2519

2520

#if defined(__GNUC__) && (defined(__i386__) || defined(__x86_64__))

2521

#define compute_bit2idx(X, I)\

2522

{\

2523

unsigned int J;\

2524

__asm__("bsfl\t%1, %0\n\t" : "=r" (J) : "g" (X));\

2525

I = (bindex_t)J;\

2526

}

2527

#elif defined(_MSC_VER) && _MSC_VER>=1300

2528

#define compute_bit2idx(X, I)\

2529

{\

2530

unsigned int J;\

2531

_BitScanForward((DWORD *) &J, X);\

2532

I = (bindex_t)J;\

2533

}

2534

2535

#else /* GNUC */

2536

#if USE_BUILTIN_FFS

2537

#define compute_bit2idx(X, I) I = ffs(X)-1

2538

2539

#else /* USE_BUILTIN_FFS */

2540

#define compute_bit2idx(X, I)\

2541

{\

2542

unsigned int Y = X - 1;\

2543

unsigned int K = Y >> (16-4) & 16;\

2544

unsigned int N = K; Y >>= K;\

2545

N += K = Y >> (8-3) & 8; Y >>= K;\

2546

N += K = Y >> (4-2) & 4; Y >>= K;\

2547

N += K = Y >> (2-1) & 2; Y >>= K;\

2548

N += K = Y >> (1-0) & 1; Y >>= K;\

2549

I = (bindex_t)(N + Y);\

2550

}

2551

#endif /* USE_BUILTIN_FFS */

2552

#endif /* GNUC */

2553

2554

/* isolate the least set bit of a bitmap */

2555

#define least_bit(x) ((x) & -(x))

2556

2557

/* mask with all bits to left of least bit of x on */

2558

#define left_bits(x) ((x<<1) | -(x<<1))

2559

2560

/* mask with all bits to left of or equal to least bit of x on */

2561

#define same_or_left_bits(x) ((x) | -(x))

2562

2563

2564

/* ----------------------- Runtime Check Support ------------------------- */

2565

2566

/*

2567

For security, the main invariant is that malloc/free/etc never

2568

writes to a static address other than malloc_state, unless static

2569

malloc_state itself has been corrupted, which cannot occur via

2570

malloc (because of these checks). In essence this means that we

2571

believe all pointers, sizes, maps etc held in malloc_state, but

2572

check all of those linked or offsetted from other embedded data

2573

structures. These checks are interspersed with main code in a way

2574

that tends to minimize their run-time cost.

2575

2576

When FOOTERS is defined, in addition to range checking, we also

2577

verify footer fields of inuse chunks, which can be used guarantee

2578

that the mstate controlling malloc/free is intact. This is a

2579

streamlined version of the approach described by William Robertson

2580

et al in "Run-time Detection of Heap-based Overflows" LISA'03

2581

http://www.usenix.org/events/lisa03/tech/robertson.html The footer

2582

of an inuse chunk holds the xor of its mstate and a random seed,

2583

that is checked upon calls to free() and realloc(). This is

2584

(probablistically) unguessable from outside the program, but can be

2585

computed by any code successfully malloc'ing any chunk, so does not

2586

itself provide protection against code that has already broken

2587

security through some other means. Unlike Robertson et al, we

2588

always dynamically check addresses of all offset chunks (previous,

2589

next, etc). This turns out to be cheaper than relying on hashes.

2590

*/

2591

2592

#if !INSECURE

2593

/* Check if address a is at least as high as any from MORECORE or MMAP */

2594

#define ok_address(M, a) ((char*)(a) >= (M)->least_addr)

2595

/* Check if address of next chunk n is higher than base chunk p */

2596

#define ok_next(p, n) ((char*)(p) < (char*)(n))

2597

/* Check if p has its cinuse bit on */

2598

#define ok_cinuse(p) cinuse(p)

2599

/* Check if p has its pinuse bit on */

2600

#define ok_pinuse(p) pinuse(p)

2601

2602

#else /* !INSECURE */

2603

#define ok_address(M, a) (1)

2604

#define ok_next(b, n) (1)

2605

#define ok_cinuse(p) (1)

2606

#define ok_pinuse(p) (1)

2607

#endif /* !INSECURE */

2608

2609

#if (FOOTERS && !INSECURE)

2610

/* Check if (alleged) mstate m has expected magic field */

2611

#define ok_magic(M) ((M)->magic == mparams.magic)

2612

#else /* (FOOTERS && !INSECURE) */

2613

#define ok_magic(M) (1)

2614

#endif /* (FOOTERS && !INSECURE) */

2615

2616

2617

/* In gcc, use __builtin_expect to minimize impact of checks */

2618

#if !INSECURE

2619

#if defined(__GNUC__) && __GNUC__ >= 3

2620

#define RTCHECK(e) __builtin_expect(e, 1)

2621

#else /* GNUC */

2622

#define RTCHECK(e) (e)

2623

#endif /* GNUC */

2624

#else /* !INSECURE */

2625

#define RTCHECK(e) (1)

2626

#endif /* !INSECURE */

2627

2628

/* macros to set up inuse chunks with or without footers */

2629

2630

#if !FOOTERS

2631

2632

#define mark_inuse_foot(M,p,s)

2633

2634

/* Set cinuse bit and pinuse bit of next chunk */

2635

#define set_inuse(M,p,s)\

2636

((p)->head = (((p)->head & PINUSE_BIT)|s|CINUSE_BIT),\

2637

((mchunkptr)(((char*)(p)) + (s)))->head |= PINUSE_BIT)

2638

2639

/* Set cinuse and pinuse of this chunk and pinuse of next chunk */

2640

#define set_inuse_and_pinuse(M,p,s)\

2641

((p)->head = (s|PINUSE_BIT|CINUSE_BIT),\

2642

((mchunkptr)(((char*)(p)) + (s)))->head |= PINUSE_BIT)

2643

2644

/* Set size, cinuse and pinuse bit of this chunk */

2645

#define set_size_and_pinuse_of_inuse_chunk(M, p, s)\

2646

((p)->head = (s|PINUSE_BIT|CINUSE_BIT))

2647

2648

#else /* FOOTERS */

2649

2650

/* Set foot of inuse chunk to be xor of mstate and seed */

2651

#define mark_inuse_foot(M,p,s)\

2652

(((mchunkptr)((char*)(p) + (s)))->prev_foot = ((size_t)(M) ^ mparams.magic))

2653

2654

#define get_mstate_for(p)\

2655

((mstate)(((mchunkptr)((char*)(p) +\

2656

(chunksize(p))))->prev_foot ^ mparams.magic))

2657

2658

#define set_inuse(M,p,s)\

2659

((p)->head = (((p)->head & PINUSE_BIT)|s|CINUSE_BIT),\

2660

(((mchunkptr)(((char*)(p)) + (s)))->head |= PINUSE_BIT), \

2661

mark_inuse_foot(M,p,s))

2662

2663

#define set_inuse_and_pinuse(M,p,s)\

2664

((p)->head = (s|PINUSE_BIT|CINUSE_BIT),\

2665

(((mchunkptr)(((char*)(p)) + (s)))->head |= PINUSE_BIT),\

2666

mark_inuse_foot(M,p,s))

2667

2668

#define set_size_and_pinuse_of_inuse_chunk(M, p, s)\

2669

((p)->head = (s|PINUSE_BIT|CINUSE_BIT),\

2670

mark_inuse_foot(M, p, s))

2671

2672

#endif /* !FOOTERS */

2673

2674

/* ---------------------------- setting mparams -------------------------- */

2675

2676

/* Initialize mparams */

2677

static int init_mparams(void) {

2678

if (mparams.page_size == 0) {

2679

size_t s;

2680

2681

mparams.mmap_threshold = DEFAULT_MMAP_THRESHOLD;

2682

mparams.trim_threshold = DEFAULT_TRIM_THRESHOLD;

2683

#if MORECORE_CONTIGUOUS

2684

mparams.default_mflags = USE_LOCK_BIT|USE_MMAP_BIT;

2685

#else /* MORECORE_CONTIGUOUS */

2686

mparams.default_mflags = USE_LOCK_BIT|USE_MMAP_BIT|USE_NONCONTIGUOUS_BIT;

2687

#endif /* MORECORE_CONTIGUOUS */

2688

2689

#if (FOOTERS && !INSECURE)

2690

{

2691

#if USE_DEV_RANDOM

2692

int fd;

2693

unsigned char buf[sizeof(size_t)];

2694

/* Try to use /dev/urandom, else fall back on using time */

2695

if ((fd = open("/dev/urandom", O_RDONLY)) >= 0 &&

2696

read(fd, buf, sizeof(buf)) == sizeof(buf)) {

2697

s = *((size_t *) buf);

2698

close(fd);

2699

}

2700

else

2701

#endif /* USE_DEV_RANDOM */

2702

s = (size_t)(time(0) ^ (size_t)0x55555555U);

2703

2704

s |= (size_t)8U; /* ensure nonzero */

2705

s &= ~(size_t)7U; /* improve chances of fault for bad values */

2706

2707

}

2708

#else /* (FOOTERS && !INSECURE) */

2709

s = (size_t)0x58585858U;

2710

#endif /* (FOOTERS && !INSECURE) */

2711

ACQUIRE_MAGIC_INIT_LOCK();

2712

if (mparams.magic == 0) {

2713

mparams.magic = s;

2714

/* Set up lock for main malloc area */

2715

INITIAL_LOCK(&gm->mutex);

2716

gm->mflags = mparams.default_mflags;

2717

}

2718

RELEASE_MAGIC_INIT_LOCK();

2719

2720

#ifndef WIN32

2721

mparams.page_size = malloc_getpagesize;

2722

mparams.granularity = ((DEFAULT_GRANULARITY != 0)?

2723

DEFAULT_GRANULARITY : mparams.page_size);

2724

#else /* WIN32 */

2725

{

2726

SYSTEM_INFO system_info;

2727

GetSystemInfo(&system_info);

2728

mparams.page_size = system_info.dwPageSize;

2729

mparams.granularity = system_info.dwAllocationGranularity;

2730

}

2731

#endif /* WIN32 */

2732

2733

/* Sanity-check configuration:

2734

size_t must be unsigned and as wide as pointer type.

2735

ints must be at least 4 bytes.

2736

alignment must be at least 8.

2737

Alignment, min chunk size, and page size must all be powers of 2.

2738

*/

2739

if ((sizeof(size_t) != sizeof(char*)) ||

2740

(MAX_SIZE_T < MIN_CHUNK_SIZE) ||

2741

(sizeof(int) < 4) ||

2742

(MALLOC_ALIGNMENT < (size_t)8U) ||

2743

((MALLOC_ALIGNMENT & (MALLOC_ALIGNMENT-SIZE_T_ONE)) != 0) ||

2744

((MCHUNK_SIZE & (MCHUNK_SIZE-SIZE_T_ONE)) != 0) ||

2745

((mparams.granularity & (mparams.granularity-SIZE_T_ONE)) != 0) ||

2746

((mparams.page_size & (mparams.page_size-SIZE_T_ONE)) != 0))

2747

ABORT;

2748

}

2749

return 0;

2750

}

2751

2752

/* support for mallopt */

2753

static int change_mparam(int param_number, int value) {

2754

size_t val = (size_t)value;

2755

init_mparams();

2756

switch(param_number) {

2757

case M_TRIM_THRESHOLD:

2758

mparams.trim_threshold = val;

2759

return 1;

2760

case M_GRANULARITY:

2761

if (val >= mparams.page_size && ((val & (val-1)) == 0)) {

2762

mparams.granularity = val;

2763

return 1;

2764

}

2765

else

2766

return 0;

2767

case M_MMAP_THRESHOLD:

2768

mparams.mmap_threshold = val;

2769

return 1;

2770

default:

2771

return 0;

2772

}

2773

}

2774

2775

#if DEBUG

2776

/* ------------------------- Debugging Support --------------------------- */

2777

2778

/* Check properties of any chunk, whether free, inuse, mmapped etc */

2779

static void do_check_any_chunk(mstate m, mchunkptr p) {

2780

assert((is_aligned(chunk2mem(p))) || (p->head == FENCEPOST_HEAD));

2781

assert(ok_address(m, p));

2782

}

2783

2784

/* Check properties of top chunk */

2785

static void do_check_top_chunk(mstate m, mchunkptr p) {

2786

msegmentptr sp = segment_holding(m, (char*)p);

2787

size_t sz = chunksize(p);

2788

assert(sp != 0);

2789

assert((is_aligned(chunk2mem(p))) || (p->head == FENCEPOST_HEAD));

2790

assert(ok_address(m, p));

2791

assert(sz == m->topsize);

2792

assert(sz > 0);

2793

assert(sz == ((sp->base + sp->size) - (char*)p) - TOP_FOOT_SIZE);

2794

assert(pinuse(p));

2795

assert(!next_pinuse(p));

2796

}

2797

2798

/* Check properties of (inuse) mmapped chunks */

2799

static void do_check_mmapped_chunk(mstate m, mchunkptr p) {

2800

size_t sz = chunksize(p);

2801

size_t len = (sz + (p->prev_foot & ~IS_MMAPPED_BIT) + MMAP_FOOT_PAD);

2802

assert(is_mmapped(p));

2803

assert(use_mmap(m));

2804

assert((is_aligned(chunk2mem(p))) || (p->head == FENCEPOST_HEAD));

2805

assert(ok_address(m, p));

2806

assert(!is_small(sz));

2807

assert((len & (mparams.page_size-SIZE_T_ONE)) == 0);

2808

assert(chunk_plus_offset(p, sz)->head == FENCEPOST_HEAD);

2809

assert(chunk_plus_offset(p, sz+SIZE_T_SIZE)->head == 0);

2810

}

2811

2812

/* Check properties of inuse chunks */

2813

static void do_check_inuse_chunk(mstate m, mchunkptr p) {

2814

do_check_any_chunk(m, p);

2815

assert(cinuse(p));

2816

assert(next_pinuse(p));

2817

/* If not pinuse and not mmapped, previous chunk has OK offset */

2818

assert(is_mmapped(p) || pinuse(p) || next_chunk(prev_chunk(p)) == p);

2819

if (is_mmapped(p))

2820

do_check_mmapped_chunk(m, p);

2821

}

2822

2823

/* Check properties of free chunks */

2824

static void do_check_free_chunk(mstate m, mchunkptr p) {

2825

size_t sz = p->head & ~(PINUSE_BIT|CINUSE_BIT);

2826

mchunkptr next = chunk_plus_offset(p, sz);

2827

do_check_any_chunk(m, p);

2828

assert(!cinuse(p));

2829

assert(!next_pinuse(p));

2830

assert (!is_mmapped(p));

2831

if (p != m->dv && p != m->top) {

2832

if (sz >= MIN_CHUNK_SIZE) {

2833

assert((sz & CHUNK_ALIGN_MASK) == 0);

2834

assert(is_aligned(chunk2mem(p)));

2835

assert(next->prev_foot == sz);

2836

assert(pinuse(p));

2837

assert (next == m->top || cinuse(next));

2838

assert(p->fd->bk == p);

2839

assert(p->bk->fd == p);

2840

}

2841

else /* markers are always of size SIZE_T_SIZE */

2842

assert(sz == SIZE_T_SIZE);

2843

}

2844

}

2845

2846

/* Check properties of malloced chunks at the point they are malloced */

2847

static void do_check_malloced_chunk(mstate m, void* mem, size_t s) {

2848

if (mem != 0) {

2849

mchunkptr p = mem2chunk(mem);

2850

size_t sz = p->head & ~(PINUSE_BIT|CINUSE_BIT);

2851

do_check_inuse_chunk(m, p);

2852

assert((sz & CHUNK_ALIGN_MASK) == 0);

2853

assert(sz >= MIN_CHUNK_SIZE);

2854

assert(sz >= s);

2855

/* unless mmapped, size is less than MIN_CHUNK_SIZE more than request */

2856

assert(is_mmapped(p) || sz < (s + MIN_CHUNK_SIZE));

2857

}

2858

}

2859

2860

/* Check a tree and its subtrees. */

2861

static void do_check_tree(mstate m, tchunkptr t) {

2862

tchunkptr head = 0;

2863

tchunkptr u = t;

2864

bindex_t tindex = t->index;

2865

size_t tsize = chunksize(t);

2866

bindex_t idx;

2867

compute_tree_index(tsize, idx);

2868

assert(tindex == idx);

2869

assert(tsize >= MIN_LARGE_SIZE);

2870

assert(tsize >= minsize_for_tree_index(idx));

2871

assert((idx == NTREEBINS-1) || (tsize < minsize_for_tree_index((idx+1))));

2872

2873

do { /* traverse through chain of same-sized nodes */

2874

do_check_any_chunk(m, ((mchunkptr)u));

2875

assert(u->index == tindex);

2876

assert(chunksize(u) == tsize);

2877

assert(!cinuse(u));

2878

assert(!next_pinuse(u));

2879

assert(u->fd->bk == u);

2880

assert(u->bk->fd == u);

2881

if (u->parent == 0) {

2882

assert(u->child[0] == 0);

2883

assert(u->child[1] == 0);

2884

}

2885

else {

2886

assert(head == 0); /* only one node on chain has parent */

2887

head = u;

2888

assert(u->parent != u);

2889

assert (u->parent->child[0] == u ||

2890

u->parent->child[1] == u ||

2891

*((tbinptr*)(u->parent)) == u);

2892

if (u->child[0] != 0) {

2893

assert(u->child[0]->parent == u);

2894

assert(u->child[0] != u);

2895

do_check_tree(m, u->child[0]);

2896

}

2897

if (u->child[1] != 0) {

2898

assert(u->child[1]->parent == u);

2899

assert(u->child[1] != u);

2900

do_check_tree(m, u->child[1]);

2901

}

2902

if (u->child[0] != 0 && u->child[1] != 0) {

2903

assert(chunksize(u->child[0]) < chunksize(u->child[1]));

2904

}

2905

}

2906

u = u->fd;

2907

} while (u != t);

2908

assert(head != 0);

2909

}

2910

2911

/* Check all the chunks in a treebin. */

2912

static void do_check_treebin(mstate m, bindex_t i) {

2913

tbinptr* tb = treebin_at(m, i);

2914

tchunkptr t = *tb;

2915

int empty = (m->treemap & (1U << i)) == 0;

2916

if (t == 0)

2917

assert(empty);

2918

if (!empty)

2919

do_check_tree(m, t);

2920

}

2921

2922

/* Check all the chunks in a smallbin. */

2923

static void do_check_smallbin(mstate m, bindex_t i) {

2924

sbinptr b = smallbin_at(m, i);

2925

mchunkptr p = b->bk;

2926

unsigned int empty = (m->smallmap & (1U << i)) == 0;

2927

if (p == b)

2928

assert(empty);

2929

if (!empty) {

2930

for (; p != b; p = p->bk) {

2931

size_t size = chunksize(p);

2932

mchunkptr q;

2933

/* each chunk claims to be free */

2934

do_check_free_chunk(m, p);

2935

/* chunk belongs in bin */

2936

assert(small_index(size) == i);

2937

assert(p->bk == b || chunksize(p->bk) == chunksize(p));

2938

/* chunk is followed by an inuse chunk */

2939

q = next_chunk(p);

2940

if (q->head != FENCEPOST_HEAD)

2941

do_check_inuse_chunk(m, q);

2942

}

2943

}

2944

}

2945

2946

/* Find x in a bin. Used in other check functions. */

2947

static int bin_find(mstate m, mchunkptr x) {

2948

size_t size = chunksize(x);

2949

if (is_small(size)) {

2950

bindex_t sidx = small_index(size);

2951

sbinptr b = smallbin_at(m, sidx);

2952

if (smallmap_is_marked(m, sidx)) {

2953

mchunkptr p = b;

2954

do {

2955

if (p == x)

2956

return 1;

2957

} while ((p = p->fd) != b);

2958

}

2959

}

2960

else {

2961

bindex_t tidx;

2962

compute_tree_index(size, tidx);

2963

if (treemap_is_marked(m, tidx)) {

2964

tchunkptr t = *treebin_at(m, tidx);

2965

size_t sizebits = size << leftshift_for_tree_index(tidx);

2966

while (t != 0 && chunksize(t) != size) {

2967

t = t->child[(sizebits >> (SIZE_T_BITSIZE-SIZE_T_ONE)) & 1];

2968

sizebits <<= 1;

2969

}

2970

if (t != 0) {

2971

tchunkptr u = t;

2972

do {

2973

if (u == (tchunkptr)x)

2974

return 1;

2975

} while ((u = u->fd) != t);

2976

}

2977

}

2978

}

2979

return 0;

2980

}

2981

2982

/* Traverse each chunk and check it; return total */

2983

static size_t traverse_and_check(mstate m) {

2984

size_t sum = 0;

2985

if (is_initialized(m)) {

2986

msegmentptr s = &m->seg;

2987

sum += m->topsize + TOP_FOOT_SIZE;

2988

while (s != 0) {

2989

mchunkptr q = align_as_chunk(s->base);

2990

mchunkptr lastq = 0;

2991

assert(pinuse(q));

2992

while (segment_holds(s, q) &&

2993

q != m->top && q->head != FENCEPOST_HEAD) {

2994

sum += chunksize(q);

2995

if (cinuse(q)) {

2996

assert(!bin_find(m, q));

2997

do_check_inuse_chunk(m, q);

2998

}

2999

else {

3000

assert(q == m->dv || bin_find(m, q));

3001

assert(lastq == 0 || cinuse(lastq)); /* Not 2 consecutive free */

3002

do_check_free_chunk(m, q);

3003

}

3004

lastq = q;

3005

q = next_chunk(q);

3006

}

3007

s = s->next;

3008

}

3009

}

3010

return sum;

3011

}

3012

3013

/* Check all properties of malloc_state. */

3014

static void do_check_malloc_state(mstate m) {

3015

bindex_t i;

3016

size_t total;

3017

/* check bins */

3018

for (i = 0; i < NSMALLBINS; ++i)

3019

do_check_smallbin(m, i);

3020

for (i = 0; i < NTREEBINS; ++i)

3021

do_check_treebin(m, i);

3022

3023

if (m->dvsize != 0) { /* check dv chunk */

3024

do_check_any_chunk(m, m->dv);

3025

assert(m->dvsize == chunksize(m->dv));

3026

assert(m->dvsize >= MIN_CHUNK_SIZE);

3027

assert(bin_find(m, m->dv) == 0);

3028

}

3029

3030

if (m->top != 0) { /* check top chunk */

3031

do_check_top_chunk(m, m->top);

3032

assert(m->topsize == chunksize(m->top));

3033

assert(m->topsize > 0);

3034

assert(bin_find(m, m->top) == 0);

3035

}

3036

3037

total = traverse_and_check(m);

3038

assert(total <= m->footprint);

3039

assert(m->footprint <= m->max_footprint);

3040

}

3041

#endif /* DEBUG */

3042

3043

/* ----------------------------- statistics ------------------------------ */

3044

3045

#if !NO_MALLINFO

3046

static struct mallinfo internal_mallinfo(mstate m) {

3047

struct mallinfo nm = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };

3048

if (!PREACTION(m)) {

3049

check_malloc_state(m);

3050

if (is_initialized(m)) {

3051

size_t nfree = SIZE_T_ONE; /* top always free */

3052

size_t mfree = m->topsize + TOP_FOOT_SIZE;

3053

size_t sum = mfree;

3054

msegmentptr s = &m->seg;

3055

while (s != 0) {

3056

mchunkptr q = align_as_chunk(s->base);

3057

while (segment_holds(s, q) &&

3058

q != m->top && q->head != FENCEPOST_HEAD) {

3059

size_t sz = chunksize(q);

3060

sum += sz;

3061

if (!cinuse(q)) {

3062

mfree += sz;

3063

++nfree;

3064

}

3065

q = next_chunk(q);

3066

}

3067

s = s->next;

3068

}

3069

3070

nm.arena = sum;

3071

nm.ordblks = nfree;

3072

nm.hblkhd = m->footprint - sum;

3073

nm.usmblks = m->max_footprint;

3074

nm.uordblks = m->footprint - mfree;

3075

nm.fordblks = mfree;

3076

nm.keepcost = m->topsize;

3077

}

3078

3079

POSTACTION(m);

3080

}

3081

return nm;

3082

}

3083

#endif /* !NO_MALLINFO */

3084

3085

static void internal_malloc_stats(mstate m) {

3086

if (!PREACTION(m)) {

3087

size_t maxfp = 0;

3088

size_t fp = 0;

3089

size_t used = 0;

3090

check_malloc_state(m);

3091

if (is_initialized(m)) {

3092

msegmentptr s = &m->seg;

3093

maxfp = m->max_footprint;

3094

fp = m->footprint;

3095

used = fp - (m->topsize + TOP_FOOT_SIZE);

3096

3097

while (s != 0) {

3098

mchunkptr q = align_as_chunk(s->base);

3099

while (segment_holds(s, q) &&

3100

q != m->top && q->head != FENCEPOST_HEAD) {

3101

if (!cinuse(q))

3102

used -= chunksize(q);

3103

q = next_chunk(q);

3104

}

3105

s = s->next;

3106

}

3107

}

3108

3109

fprintf(stderr, "max system bytes = %10lu\n", (unsigned long)(maxfp));

3110

fprintf(stderr, "system bytes = %10lu\n", (unsigned long)(fp));

3111

fprintf(stderr, "in use bytes = %10lu\n", (unsigned long)(used));

3112

3113

POSTACTION(m);

3114

}

3115

}

3116

3117

/* ----------------------- Operations on smallbins ----------------------- */

3118

3119

/*

3120

Various forms of linking and unlinking are defined as macros. Even

3121

the ones for trees, which are very long but have very short typical

3122

paths. This is ugly but reduces reliance on inlining support of

3123

compilers.

3124

*/

3125

3126

/* Link a free chunk into a smallbin */

3127

#define insert_small_chunk(M, P, S) {\

3128

bindex_t I = small_index(S);\

3129

mchunkptr B = smallbin_at(M, I);\

3130

mchunkptr F = B;\

3131

assert(S >= MIN_CHUNK_SIZE);\

3132

if (!smallmap_is_marked(M, I))\

3133

mark_smallmap(M, I);\

3134

else if (RTCHECK(ok_address(M, B->fd)))\

3135

F = B->fd;\

3136

else {\

3137

CORRUPTION_ERROR_ACTION(M);\

3138

}\

3139

B->fd = P;\

3140

F->bk = P;\

3141

P->fd = F;\

3142

P->bk = B;\

3143

}

3144

3145

/* Unlink a chunk from a smallbin */

3146

#define unlink_small_chunk(M, P, S) {\

3147

mchunkptr F = P->fd;\

3148

mchunkptr B = P->bk;\

3149

bindex_t I = small_index(S);\

3150

assert(P != B);\

3151

assert(P != F);\

3152

assert(chunksize(P) == small_index2size(I));\

3153

if (F == B)\

3154

clear_smallmap(M, I);\

3155

else if (RTCHECK((F == smallbin_at(M,I) || ok_address(M, F)) &&\

3156

(B == smallbin_at(M,I) || ok_address(M, B)))) {\

3157

F->bk = B;\

3158

B->fd = F;\

3159

}\

3160

else {\

3161

CORRUPTION_ERROR_ACTION(M);\

3162

}\

3163

}

3164

3165

/* Unlink the first chunk from a smallbin */

3166

#define unlink_first_small_chunk(M, B, P, I) {\

3167

mchunkptr F = P->fd;\

3168

assert(P != B);\

3169

assert(P != F);\

3170

assert(chunksize(P) == small_index2size(I));\

3171

if (B == F)\

3172

clear_smallmap(M, I);\

3173

else if (RTCHECK(ok_address(M, F))) {\

3174

B->fd = F;\

3175

F->bk = B;\

3176

}\

3177

else {\

3178

CORRUPTION_ERROR_ACTION(M);\

3179

}\

3180

}

3181

3182

/* Replace dv node, binning the old one */

3183

/* Used only when dvsize known to be small */

3184

#define replace_dv(M, P, S) {\

3185

size_t DVS = M->dvsize;\

3186

if (DVS != 0) {\

3187

mchunkptr DV = M->dv;\

3188

assert(is_small(DVS));\

3189

insert_small_chunk(M, DV, DVS);\

3190

}\

3191

M->dvsize = S;\

3192

M->dv = P;\

3193

}

3194

3195

/* ------------------------- Operations on trees ------------------------- */

3196

3197

/* Insert chunk into tree */

3198

#define insert_large_chunk(M, X, S) {\

3199

tbinptr* H;\

3200

bindex_t I;\

3201

compute_tree_index(S, I);\

3202

H = treebin_at(M, I);\

3203

X->index = I;\

3204

X->child[0] = X->child[1] = 0;\

3205

if (!treemap_is_marked(M, I)) {\

3206

mark_treemap(M, I);\

3207

*H = X;\

3208

X->parent = (tchunkptr)H;\

3209

X->fd = X->bk = X;\

3210

}\

3211

else {\

3212

tchunkptr T = *H;\

3213

size_t K = S << leftshift_for_tree_index(I);\

3214

for (;;) {\

3215

if (chunksize(T) != S) {\

3216

tchunkptr* C = &(T->child[(K >> (SIZE_T_BITSIZE-SIZE_T_ONE)) & 1]);\

3217

K <<= 1;\

3218

if (*C != 0)\

3219

T = *C;\

3220

else if (RTCHECK(ok_address(M, C))) {\

3221

*C = X;\

3222

X->parent = T;\

3223

X->fd = X->bk = X;\

3224

break;\

3225

}\

3226

else {\

3227

CORRUPTION_ERROR_ACTION(M);\

3228

break;\

3229

}\

3230

}\

3231

else {\

3232

tchunkptr F = T->fd;\

3233

if (RTCHECK(ok_address(M, T) && ok_address(M, F))) {\

3234

T->fd = F->bk = X;\

3235

X->fd = F;\

3236

X->bk = T;\

3237

X->parent = 0;\

3238

break;\

3239

}\

3240

else {\

3241

CORRUPTION_ERROR_ACTION(M);\

3242

break;\

3243

}\

3244

}\

3245

}\

3246

}\

3247

}

3248

3249

/*

3250

Unlink steps:

3251

3252

1. If x is a chained node, unlink it from its same-sized fd/bk links

3253

and choose its bk node as its replacement.

3254

2. If x was the last node of its size, but not a leaf node, it must

3255

be replaced with a leaf node (not merely one with an open left or

3256

right), to make sure that lefts and rights of descendents

3257

correspond properly to bit masks. We use the rightmost descendent

3258

of x. We could use any other leaf, but this is easy to locate and

3259

tends to counteract removal of leftmosts elsewhere, and so keeps

3260

paths shorter than minimally guaranteed. This doesn't loop much

3261

because on average a node in a tree is near the bottom.

3262

3. If x is the base of a chain (i.e., has parent links) relink

3263

x's parent and children to x's replacement (or null if none).

3264

*/

3265

3266

#define unlink_large_chunk(M, X) {\

3267

tchunkptr XP = X->parent;\

3268

tchunkptr R;\

3269

if (X->bk != X) {\

3270

tchunkptr F = X->fd;\

3271

R = X->bk;\

3272

if (RTCHECK(ok_address(M, F))) {\

3273

F->bk = R;\

3274

R->fd = F;\

3275

}\

3276

else {\

3277

CORRUPTION_ERROR_ACTION(M);\

3278

}\

3279

}\

3280

else {\

3281

tchunkptr* RP;\

3282

if (((R = *(RP = &(X->child[1]))) != 0) ||\

3283

((R = *(RP = &(X->child[0]))) != 0)) {\

3284

tchunkptr* CP;\

3285

while ((*(CP = &(R->child[1])) != 0) ||\

3286

(*(CP = &(R->child[0])) != 0)) {\

3287

R = *(RP = CP);\

3288

}\

3289

if (RTCHECK(ok_address(M, RP)))\

3290

*RP = 0;\

3291

else {\

3292

CORRUPTION_ERROR_ACTION(M);\

3293

}\

3294

}\

3295

}\

3296

if (XP != 0) {\

3297

tbinptr* H = treebin_at(M, X->index);\

3298

if (X == *H) {\

3299

if ((*H = R) == 0) \

3300

clear_treemap(M, X->index);\

3301

}\

3302

else if (RTCHECK(ok_address(M, XP))) {\

3303

if (XP->child[0] == X) \

3304

XP->child[0] = R;\

3305

else \

3306

XP->child[1] = R;\

3307

}\

3308

else\

3309

CORRUPTION_ERROR_ACTION(M);\

3310

if (R != 0) {\

3311

if (RTCHECK(ok_address(M, R))) {\

3312

tchunkptr C0, C1;\

3313

R->parent = XP;\

3314

if ((C0 = X->child[0]) != 0) {\

3315

if (RTCHECK(ok_address(M, C0))) {\

3316

R->child[0] = C0;\

3317

C0->parent = R;\

3318

}\

3319

else\

3320

CORRUPTION_ERROR_ACTION(M);\

3321

}\

3322

if ((C1 = X->child[1]) != 0) {\

3323

if (RTCHECK(ok_address(M, C1))) {\

3324

R->child[1] = C1;\

3325

C1->parent = R;\

3326

}\

3327

else\

3328

CORRUPTION_ERROR_ACTION(M);\

3329

}\

3330

}\

3331

else\

3332

CORRUPTION_ERROR_ACTION(M);\

3333

}\

3334

}\

3335

}

3336

3337

/* Relays to large vs small bin operations */

3338

3339

#define insert_chunk(M, P, S)\

3340

if (is_small(S)) insert_small_chunk(M, P, S)\

3341

else { tchunkptr TP = (tchunkptr)(P); insert_large_chunk(M, TP, S); }

3342

3343

#define unlink_chunk(M, P, S)\

3344

if (is_small(S)) unlink_small_chunk(M, P, S)\

3345

else { tchunkptr TP = (tchunkptr)(P); unlink_large_chunk(M, TP); }

3346

3347

3348

/* Relays to internal calls to malloc/free from realloc, memalign etc */

3349

3350

#if ONLY_MSPACES

3351

#define internal_malloc(m, b) mspace_malloc(m, b)

3352

#define internal_free(m, mem) mspace_free(m,mem);

3353

#else /* ONLY_MSPACES */

3354

#if MSPACES

3355

#define internal_malloc(m, b)\

3356

(m == gm)? dlmalloc(b) : mspace_malloc(m, b)

3357

#define internal_free(m, mem)\

3358

if (m == gm) dlfree(mem); else mspace_free(m,mem);

3359

#else /* MSPACES */

3360

#define internal_malloc(m, b) dlmalloc(b)

3361

#define internal_free(m, mem) dlfree(mem)

3362

#endif /* MSPACES */

3363

#endif /* ONLY_MSPACES */

3364

3365

/* ----------------------- Direct-mmapping chunks ----------------------- */

3366

3367

/*

3368

Directly mmapped chunks are set up with an offset to the start of

3369

the mmapped region stored in the prev_foot field of the chunk. This

3370

allows reconstruction of the required argument to MUNMAP when freed,

3371

and also allows adjustment of the returned chunk to meet alignment

3372

requirements (especially in memalign). There is also enough space

3373

allocated to hold a fake next chunk of size SIZE_T_SIZE to maintain

3374

the PINUSE bit so frees can be checked.

3375

*/

3376

3377

/* Malloc using mmap */

3378

static void* mmap_alloc(mstate m, size_t nb) {

3379

size_t mmsize = granularity_align(nb + SIX_SIZE_T_SIZES + CHUNK_ALIGN_MASK);

3380

if (mmsize > nb) { /* Check for wrap around 0 */

3381

char* mm = (char*)(DIRECT_MMAP(mmsize));

3382

if (mm != CMFAIL) {

3383

size_t offset = align_offset(chunk2mem(mm));

3384

size_t psize = mmsize - offset - MMAP_FOOT_PAD;

3385

mchunkptr p = (mchunkptr)(mm + offset);

3386

p->prev_foot = offset | IS_MMAPPED_BIT;

3387

(p)->head = (psize|CINUSE_BIT);

3388

mark_inuse_foot(m, p, psize);

3389

chunk_plus_offset(p, psize)->head = FENCEPOST_HEAD;

3390

chunk_plus_offset(p, psize+SIZE_T_SIZE)->head = 0;

3391

3392

if (mm < m->least_addr)

3393

m->least_addr = mm;

3394

if ((m->footprint += mmsize) > m->max_footprint)

3395

m->max_footprint = m->footprint;

3396

assert(is_aligned(chunk2mem(p)));

3397

check_mmapped_chunk(m, p);

3398

return chunk2mem(p);

3399

}

3400

}

3401

return 0;

3402

}

3403

3404

/* Realloc using mmap */

3405

static mchunkptr mmap_resize(mstate m, mchunkptr oldp, size_t nb) {

3406

size_t oldsize = chunksize(oldp);

3407

if (is_small(nb)) /* Can't shrink mmap regions below small size */

3408

return 0;

3409

/* Keep old chunk if big enough but not too big */

3410

if (oldsize >= nb + SIZE_T_SIZE &&

3411

(oldsize - nb) <= (mparams.granularity << 1))

3412

return oldp;

3413

else {

3414

size_t offset = oldp->prev_foot & ~IS_MMAPPED_BIT;

3415

size_t oldmmsize = oldsize + offset + MMAP_FOOT_PAD;

3416

size_t newmmsize = granularity_align(nb + SIX_SIZE_T_SIZES +

3417

CHUNK_ALIGN_MASK);

3418

char* cp = (char*)CALL_MREMAP((char*)oldp - offset,

3419

oldmmsize, newmmsize, 1);

3420

if (cp != CMFAIL) {

3421

mchunkptr newp = (mchunkptr)(cp + offset);

3422

size_t psize = newmmsize - offset - MMAP_FOOT_PAD;

3423

newp->head = (psize|CINUSE_BIT);

3424

mark_inuse_foot(m, newp, psize);

3425

chunk_plus_offset(newp, psize)->head = FENCEPOST_HEAD;

3426

chunk_plus_offset(newp, psize+SIZE_T_SIZE)->head = 0;

3427

3428

if (cp < m->least_addr)

3429

m->least_addr = cp;

3430

if ((m->footprint += newmmsize - oldmmsize) > m->max_footprint)

3431

m->max_footprint = m->footprint;

3432

check_mmapped_chunk(m, newp);

3433

return newp;

3434

}

3435

}

3436

return 0;

3437

}

3438

3439

/* -------------------------- mspace management -------------------------- */

3440

3441

/* Initialize top chunk and its size */

3442

static void init_top(mstate m, mchunkptr p, size_t psize) {

3443

/* Ensure alignment */

3444

size_t offset = align_offset(chunk2mem(p));

3445

p = (mchunkptr)((char*)p + offset);

3446

psize -= offset;

3447

3448

m->top = p;

3449

m->topsize = psize;

3450

p->head = psize | PINUSE_BIT;

3451

/* set size of fake trailing chunk holding overhead space only once */

3452

chunk_plus_offset(p, psize)->head = TOP_FOOT_SIZE;

3453

m->trim_check = mparams.trim_threshold; /* reset on each update */

3454

}

3455

3456

/* Initialize bins for a new mstate that is otherwise zeroed out */

3457

static void init_bins(mstate m) {

3458

/* Establish circular links for smallbins */

3459

bindex_t i;

3460

for (i = 0; i < NSMALLBINS; ++i) {

3461

sbinptr bin = smallbin_at(m,i);

3462

bin->fd = bin->bk = bin;

3463

}

3464

}

3465

3466

#if PROCEED_ON_ERROR

3467

3468

/* default corruption action */

3469

static void reset_on_error(mstate m) {

3470

int i;

3471

++malloc_corruption_error_count;

3472

/* Reinitialize fields to forget about all memory */

3473

m->smallbins = m->treebins = 0;

3474

m->dvsize = m->topsize = 0;

3475

m->seg.base = 0;

3476

m->seg.size = 0;

3477

m->seg.next = 0;

3478

m->top = m->dv = 0;

3479

for (i = 0; i < NTREEBINS; ++i)

3480

*treebin_at(m, i) = 0;

3481

init_bins(m);

3482

}

3483

#endif /* PROCEED_ON_ERROR */

3484

3485

/* Allocate chunk and prepend remainder with chunk in successor base. */

3486

static void* prepend_alloc(mstate m, char* newbase, char* oldbase,

3487

size_t nb) {

3488

mchunkptr p = align_as_chunk(newbase);

3489

mchunkptr oldfirst = align_as_chunk(oldbase);

3490

size_t psize = (char*)oldfirst - (char*)p;

3491

mchunkptr q = chunk_plus_offset(p, nb);

3492

size_t qsize = psize - nb;

3493

set_size_and_pinuse_of_inuse_chunk(m, p, nb);

3494

3495

assert((char*)oldfirst > (char*)q);

3496

assert(pinuse(oldfirst));

3497

assert(qsize >= MIN_CHUNK_SIZE);

3498

3499

/* consolidate remainder with first chunk of old base */

3500

if (oldfirst == m->top) {

3501

size_t tsize = m->topsize += qsize;

3502

m->top = q;

3503

q->head = tsize | PINUSE_BIT;

3504

check_top_chunk(m, q);

3505

}

3506

else if (oldfirst == m->dv) {

3507

size_t dsize = m->dvsize += qsize;

3508

m->dv = q;

3509

set_size_and_pinuse_of_free_chunk(q, dsize);

3510

}

3511

else {

3512

if (!cinuse(oldfirst)) {

3513

size_t nsize = chunksize(oldfirst);

3514

unlink_chunk(m, oldfirst, nsize);

3515

oldfirst = chunk_plus_offset(oldfirst, nsize);

3516

qsize += nsize;

3517

}

3518

set_free_with_pinuse(q, qsize, oldfirst);

3519

insert_chunk(m, q, qsize);

3520

check_free_chunk(m, q);

3521

}

3522

3523

check_malloced_chunk(m, chunk2mem(p), nb);

3524

return chunk2mem(p);

3525

}

3526

3527

3528

/* Add a segment to hold a new noncontiguous region */

3529

static void add_segment(mstate m, char* tbase, size_t tsize, flag_t mmapped) {

3530

/* Determine locations and sizes of segment, fenceposts, old top */

3531

char* old_top = (char*)m->top;

3532

msegmentptr oldsp = segment_holding(m, old_top);

3533

char* old_end = oldsp->base + oldsp->size;

3534

size_t ssize = pad_request(sizeof(struct malloc_segment));

3535

char* rawsp = old_end - (ssize + FOUR_SIZE_T_SIZES + CHUNK_ALIGN_MASK);

3536

size_t offset = align_offset(chunk2mem(rawsp));

3537

char* asp = rawsp + offset;

3538

char* csp = (asp < (old_top + MIN_CHUNK_SIZE))? old_top : asp;

3539

mchunkptr sp = (mchunkptr)csp;

3540

msegmentptr ss = (msegmentptr)(chunk2mem(sp));

3541

mchunkptr tnext = chunk_plus_offset(sp, ssize);

3542

mchunkptr p = tnext;

3543

int nfences = 0;

3544

3545

/* reset top to new space */

3546

init_top(m, (mchunkptr)tbase, tsize - TOP_FOOT_SIZE);

3547

3548

/* Set up segment record */

3549

assert(is_aligned(ss));

3550

set_size_and_pinuse_of_inuse_chunk(m, sp, ssize);

3551

*ss = m->seg; /* Push current record */

3552

m->seg.base = tbase;

3553

m->seg.size = tsize;

3554

m->seg.sflags = mmapped;

3555

m->seg.next = ss;

3556

3557

/* Insert trailing fenceposts */

3558

for (;;) {

3559

mchunkptr nextp = chunk_plus_offset(p, SIZE_T_SIZE);

3560

p->head = FENCEPOST_HEAD;

3561

++nfences;

3562

if ((char*)(&(nextp->head)) < old_end)

3563

p = nextp;

3564

else

3565

break;

3566

}

3567

assert(nfences >= 2);

3568

3569

/* Insert the rest of old top into a bin as an ordinary free chunk */

3570

if (csp != old_top) {

3571

mchunkptr q = (mchunkptr)old_top;

3572

size_t psize = csp - old_top;

3573

mchunkptr tn = chunk_plus_offset(q, psize);

3574

set_free_with_pinuse(q, psize, tn);

3575

insert_chunk(m, q, psize);

3576

}

3577

3578

check_top_chunk(m, m->top);

3579

}

3580

3581

/* -------------------------- System allocation -------------------------- */

3582

3583

/* Get memory from system using MORECORE or MMAP */

3584

static void* sys_alloc(mstate m, size_t nb) {

3585

char* tbase = CMFAIL;

3586

size_t tsize = 0;

3587

flag_t mmap_flag = 0;

3588

3589

init_mparams();

3590

3591

/* Directly map large chunks */

3592

if (use_mmap(m) && nb >= mparams.mmap_threshold) {

3593

void* mem = mmap_alloc(m, nb);

3594

if (mem != 0)

3595

return mem;

3596

}

3597

3598

/*

3599

Try getting memory in any of three ways (in most-preferred to

3600

least-preferred order):

3601

1. A call to MORECORE that can normally contiguously extend memory.

3602

(disabled if not MORECORE_CONTIGUOUS or not HAVE_MORECORE or

3603

or main space is mmapped or a previous contiguous call failed)

3604

2. A call to MMAP new space (disabled if not HAVE_MMAP).

3605

Note that under the default settings, if MORECORE is unable to

3606

fulfill a request, and HAVE_MMAP is true, then mmap is

3607

used as a noncontiguous system allocator. This is a useful backup

3608

strategy for systems with holes in address spaces -- in this case

3609

sbrk cannot contiguously expand the heap, but mmap may be able to

3610

find space.

3611

3. A call to MORECORE that cannot usually contiguously extend memory.

3612

(disabled if not HAVE_MORECORE)

3613

*/

3614

3615

if (MORECORE_CONTIGUOUS && !use_noncontiguous(m)) {

3616

char* br = CMFAIL;

3617

msegmentptr ss = (m->top == 0)? 0 : segment_holding(m, (char*)m->top);

3618

size_t asize = 0;

3619

ACQUIRE_MORECORE_LOCK();

3620

3621

if (ss == 0) { /* First time through or recovery */

3622

char* base = (char*)CALL_MORECORE(0);

3623

if (base != CMFAIL) {

3624

asize = granularity_align(nb + TOP_FOOT_SIZE + SIZE_T_ONE);

3625

/* Adjust to end on a page boundary */

3626

if (!is_page_aligned(base))

3627

asize += (page_align((size_t)base) - (size_t)base);

3628

/* Can't call MORECORE if size is negative when treated as signed */

3629

if (asize < HALF_MAX_SIZE_T &&

3630

(br = (char*)(CALL_MORECORE(asize))) == base) {

3631

tbase = base;

3632

tsize = asize;

3633

}

3634

}

3635

}

3636

else {

3637

/* Subtract out existing available top space from MORECORE request. */

3638

asize = granularity_align(nb - m->topsize + TOP_FOOT_SIZE + SIZE_T_ONE);

3639

/* Use mem here only if it did continuously extend old space */

3640

if (asize < HALF_MAX_SIZE_T &&

3641

(br = (char*)(CALL_MORECORE(asize))) == ss->base+ss->size) {

3642

tbase = br;

3643

tsize = asize;

3644

}

3645

}

3646

3647

if (tbase == CMFAIL) { /* Cope with partial failure */

3648

if (br != CMFAIL) { /* Try to use/extend the space we did get */

3649

if (asize < HALF_MAX_SIZE_T &&

3650

asize < nb + TOP_FOOT_SIZE + SIZE_T_ONE) {

3651

size_t esize = granularity_align(nb + TOP_FOOT_SIZE + SIZE_T_ONE - asize);

3652

if (esize < HALF_MAX_SIZE_T) {

3653

char* end = (char*)CALL_MORECORE(esize);

3654

if (end != CMFAIL)

3655

asize += esize;

3656

else { /* Can't use; try to release */

3657

(void) CALL_MORECORE(-asize);

3658

br = CMFAIL;

3659

}

3660

}

3661

}

3662

}

3663

if (br != CMFAIL) { /* Use the space we did get */

3664

tbase = br;

3665

tsize = asize;

3666

}

3667

else

3668

disable_contiguous(m); /* Don't try contiguous path in the future */

3669

}

3670

3671

RELEASE_MORECORE_LOCK();

3672

}

3673

3674

if (HAVE_MMAP && tbase == CMFAIL) { /* Try MMAP */

3675

size_t req = nb + TOP_FOOT_SIZE + SIZE_T_ONE;

3676

size_t rsize = granularity_align(req);

3677

if (rsize > nb) { /* Fail if wraps around zero */

3678

char* mp = (char*)(CALL_MMAP(rsize));

3679

if (mp != CMFAIL) {

3680

tbase = mp;

3681

tsize = rsize;

3682

mmap_flag = IS_MMAPPED_BIT;

3683

}

3684

}

3685

}

3686

3687

if (HAVE_MORECORE && tbase == CMFAIL) { /* Try noncontiguous MORECORE */

3688

size_t asize = granularity_align(nb + TOP_FOOT_SIZE + SIZE_T_ONE);

3689

if (asize < HALF_MAX_SIZE_T) {

3690

char* br = CMFAIL;

3691

char* end = CMFAIL;

3692

ACQUIRE_MORECORE_LOCK();

3693

br = (char*)(CALL_MORECORE(asize));

3694

end = (char*)(CALL_MORECORE(0));

3695

RELEASE_MORECORE_LOCK();

3696

if (br != CMFAIL && end != CMFAIL && br < end) {

3697

size_t ssize = end - br;

3698

if (ssize > nb + TOP_FOOT_SIZE) {

3699

tbase = br;

3700

tsize = ssize;

3701

}

3702

}

3703

}

3704

}

3705

3706

if (tbase != CMFAIL) {

3707

3708

if ((m->footprint += tsize) > m->max_footprint)

3709

m->max_footprint = m->footprint;

3710

3711

if (!is_initialized(m)) { /* first-time initialization */

3712

m->seg.base = m->least_addr = tbase;

3713

m->seg.size = tsize;

3714

m->seg.sflags = mmap_flag;

3715

m->magic = mparams.magic;

3716

init_bins(m);

3717

if (is_global(m))

3718

init_top(m, (mchunkptr)tbase, tsize - TOP_FOOT_SIZE);

3719

else {

3720

/* Offset top by embedded malloc_state */

3721

mchunkptr mn = next_chunk(mem2chunk(m));

3722

init_top(m, mn, (size_t)((tbase + tsize) - (char*)mn) -TOP_FOOT_SIZE);

3723

}

3724

}

3725

3726

else {

3727

/* Try to merge with an existing segment */

3728

#ifdef DONT_MERGE_SEGMENTS

3729

(void) prepend_alloc;

3730

add_segment(m, tbase, tsize, mmap_flag);

3731

#else

3732

msegmentptr sp = &m->seg;

3733

while (sp != 0 && tbase != sp->base + sp->size)

3734

sp = sp->next;

3735

if (sp != 0 &&

3736

!is_extern_segment(sp) &&

3737

(sp->sflags & IS_MMAPPED_BIT) == mmap_flag &&

3738

segment_holds(sp, m->top)) { /* append */

3739

sp->size += tsize;

3740

init_top(m, m->top, m->topsize + tsize);

3741

}

3742

else {

3743

if (tbase < m->least_addr)

3744

m->least_addr = tbase;

3745

sp = &m->seg;

3746

while (sp != 0 && sp->base != tbase + tsize)

3747

sp = sp->next;

3748

if (sp != 0 &&

3749

!is_extern_segment(sp) &&

3750

(sp->sflags & IS_MMAPPED_BIT) == mmap_flag) {

3751

char* oldbase = sp->base;

3752

sp->base = tbase;

3753

sp->size += tsize;

3754

return prepend_alloc(m, tbase, oldbase, nb);

3755

}

3756

else

3757

add_segment(m, tbase, tsize, mmap_flag);

3758

}

3759

#endif /* DONT_MERGE_SEGMENTS */

3760

}

3761

3762

if (nb < m->topsize) { /* Allocate from new or extended top space */

3763

size_t rsize = m->topsize -= nb;

3764

mchunkptr p = m->top;

3765

mchunkptr r = m->top = chunk_plus_offset(p, nb);

3766

r->head = rsize | PINUSE_BIT;

3767

set_size_and_pinuse_of_inuse_chunk(m, p, nb);

3768

check_top_chunk(m, m->top);

3769

check_malloced_chunk(m, chunk2mem(p), nb);

3770

return chunk2mem(p);

3771

}

3772

}

3773

3774

MALLOC_FAILURE_ACTION;

3775

return 0;

3776

}

3777

3778

/* ----------------------- system deallocation -------------------------- */

3779

3780

/* Unmap and unlink any mmapped segments that don't contain used chunks */

3781

static size_t release_unused_segments(mstate m) {

3782

size_t released = 0;

3783

msegmentptr pred = &m->seg;

3784

msegmentptr sp = pred->next;

3785

while (sp != 0) {

3786

char* base = sp->base;

3787

size_t size = sp->size;

3788

msegmentptr next = sp->next;

3789

if (is_mmapped_segment(sp) && !is_extern_segment(sp)) {

3790

mchunkptr p = align_as_chunk(base);

3791

size_t psize = chunksize(p);

3792

/* Can unmap if first chunk holds entire segment and not pinned */

3793

if (!cinuse(p) && (char*)p + psize >= base + size - TOP_FOOT_SIZE) {

3794

tchunkptr tp = (tchunkptr)p;

3795

assert(segment_holds(sp, (char*)sp));

3796

if (p == m->dv) {

3797

m->dv = 0;

3798

m->dvsize = 0;

3799

}

3800

else {

3801

unlink_large_chunk(m, tp);

3802

}

3803

if (CALL_MUNMAP(base, size) == 0) {

3804

released += size;

3805

m->footprint -= size;

3806

/* unlink obsoleted record */

3807

sp = pred;

3808

sp->next = next;

3809

}

3810

else { /* back out if cannot unmap */

3811

insert_large_chunk(m, tp, psize);

3812

}

3813

}

3814

}

3815

pred = sp;

3816

sp = next;

3817

}

3818

return released;

3819

}

3820

3821

static int sys_trim(mstate m, size_t pad) {

3822

size_t released = 0;

3823

if (pad < MAX_REQUEST && is_initialized(m)) {

3824

pad += TOP_FOOT_SIZE; /* ensure enough room for segment overhead */

3825

3826

if (m->topsize > pad) {

3827

/* Shrink top space in granularity-size units, keeping at least one */

3828

size_t unit = mparams.granularity;

3829

size_t extra = ((m->topsize - pad + (unit - SIZE_T_ONE)) / unit -

3830

SIZE_T_ONE) * unit;

3831

msegmentptr sp = segment_holding(m, (char*)m->top);

3832

3833

if (!is_extern_segment(sp)) {

3834

if (is_mmapped_segment(sp)) {

3835

if (HAVE_MMAP &&

3836

sp->size >= extra &&

3837

!has_segment_link(m, sp)) { /* can't shrink if pinned */

3838

size_t newsize = sp->size - extra;

3839

/* Prefer mremap, fall back to munmap */

3840

if ((CALL_MREMAP(sp->base, sp->size, newsize, 0) != MFAIL) ||

3841

(CALL_MUNMAP(sp->base + newsize, extra) == 0)) {

3842

released = extra;

3843

}

3844

}

3845

}

3846

else if (HAVE_MORECORE) {

3847

if (extra >= HALF_MAX_SIZE_T) /* Avoid wrapping negative */

3848

extra = (HALF_MAX_SIZE_T) + SIZE_T_ONE - unit;

3849

ACQUIRE_MORECORE_LOCK();

3850

{

3851

/* Make sure end of memory is where we last set it. */

3852

char* old_br = (char*)(CALL_MORECORE(0));

3853

if (old_br == sp->base + sp->size) {

3854

char* rel_br = (char*)(CALL_MORECORE(-extra));

3855

char* new_br = (char*)(CALL_MORECORE(0));

3856

if (rel_br != CMFAIL && new_br < old_br)

3857

released = old_br - new_br;

3858

}

3859

}

3860

RELEASE_MORECORE_LOCK();

3861

}

3862

}

3863

3864

if (released != 0) {

3865

sp->size -= released;

3866

m->footprint -= released;

3867

init_top(m, m->top, m->topsize - released);

3868

check_top_chunk(m, m->top);

3869

}

3870

}

3871

3872

/* Unmap any unused mmapped segments */

3873

if (HAVE_MMAP)

3874

released += release_unused_segments(m);

3875

3876

/* On failure, disable autotrim to avoid repeated failed future calls */

3877

if (released == 0)

3878

m->trim_check = MAX_SIZE_T;

3879

}

3880

3881

return (released != 0)? 1 : 0;

3882

}

3883

3884

/* ---------------------------- malloc support --------------------------- */

3885

3886

/* allocate a large request from the best fitting chunk in a treebin */

3887

static void* tmalloc_large(mstate m, size_t nb) {

3888

tchunkptr v = 0;

3889

size_t rsize = -nb; /* Unsigned negation */

3890

tchunkptr t;

3891

bindex_t idx;

3892

compute_tree_index(nb, idx);

3893

3894

if ((t = *treebin_at(m, idx)) != 0) {

3895

/* Traverse tree for this bin looking for node with size == nb */

3896

size_t sizebits = nb << leftshift_for_tree_index(idx);

3897

tchunkptr rst = 0; /* The deepest untaken right subtree */

3898

for (;;) {

3899

tchunkptr rt;

3900

size_t trem = chunksize(t) - nb;

3901

if (trem < rsize) {

3902

v = t;

3903

if ((rsize = trem) == 0)

3904

break;

3905

}

3906

rt = t->child[1];

3907

t = t->child[(sizebits >> (SIZE_T_BITSIZE-SIZE_T_ONE)) & 1];

3908

if (rt != 0 && rt != t)

3909

rst = rt;

3910

if (t == 0) {

3911

t = rst; /* set t to least subtree holding sizes > nb */

3912

break;

3913

}

3914

sizebits <<= 1;

3915

}

3916

}

3917

3918

if (t == 0 && v == 0) { /* set t to root of next non-empty treebin */

3919

binmap_t leftbits = left_bits(idx2bit(idx)) & m->treemap;

3920

if (leftbits != 0) {

3921

bindex_t i;

3922

binmap_t leastbit = least_bit(leftbits);

3923

compute_bit2idx(leastbit, i);

3924

t = *treebin_at(m, i);

3925

}

3926

}

3927

3928

while (t != 0) { /* find smallest of tree or subtree */

3929

size_t trem = chunksize(t) - nb;

3930

if (trem < rsize) {

3931

rsize = trem;

3932

v = t;

3933

}

3934

t = leftmost_child(t);

3935

}

3936

3937

/* If dv is a better fit, return 0 so malloc will use it */

3938

if (v != 0 && rsize < (size_t)(m->dvsize - nb)) {

3939

if (RTCHECK(ok_address(m, v))) { /* split */

3940

mchunkptr r = chunk_plus_offset(v, nb);

3941

assert(chunksize(v) == rsize + nb);

3942

if (RTCHECK(ok_next(v, r))) {

3943

unlink_large_chunk(m, v);

3944

if (rsize < MIN_CHUNK_SIZE)

3945

set_inuse_and_pinuse(m, v, (rsize + nb));

3946

else {

3947

set_size_and_pinuse_of_inuse_chunk(m, v, nb);

3948

set_size_and_pinuse_of_free_chunk(r, rsize);

3949

insert_chunk(m, r, rsize);

3950

}

3951

return chunk2mem(v);

3952

}

3953

}

3954

CORRUPTION_ERROR_ACTION(m);

3955

}

3956

return 0;

3957

}

3958

3959

/* allocate a small request from the best fitting chunk in a treebin */

3960

static void* tmalloc_small(mstate m, size_t nb) {

3961

tchunkptr t, v;

3962

size_t rsize;

3963

bindex_t i;

3964

binmap_t leastbit = least_bit(m->treemap);

3965

compute_bit2idx(leastbit, i);

3966

3967

v = t = *treebin_at(m, i);

3968

rsize = chunksize(t) - nb;

3969

3970

while ((t = leftmost_child(t)) != 0) {

3971

size_t trem = chunksize(t) - nb;

3972

if (trem < rsize) {

3973

rsize = trem;

3974

v = t;

3975

}

3976

}

3977

3978

if (RTCHECK(ok_address(m, v))) {

3979

mchunkptr r = chunk_plus_offset(v, nb);

3980

assert(chunksize(v) == rsize + nb);

3981

if (RTCHECK(ok_next(v, r))) {

3982

unlink_large_chunk(m, v);

3983

if (rsize < MIN_CHUNK_SIZE)

3984

set_inuse_and_pinuse(m, v, (rsize + nb));

3985

else {

3986

set_size_and_pinuse_of_inuse_chunk(m, v, nb);

3987

set_size_and_pinuse_of_free_chunk(r, rsize);

3988

replace_dv(m, r, rsize);

3989

}

3990

return chunk2mem(v);

3991

}

3992

}

3993

3994

CORRUPTION_ERROR_ACTION(m);

3995

return 0;

3996

}

3997

3998

/* --------------------------- realloc support --------------------------- */

3999

4000

static void* internal_realloc(mstate m, void* oldmem, size_t bytes) {

4001

if (bytes >= MAX_REQUEST) {

4002

MALLOC_FAILURE_ACTION;

4003

return 0;

4004

}

4005

if (!PREACTION(m)) {

4006

mchunkptr oldp = mem2chunk(oldmem);

4007

size_t oldsize = chunksize(oldp);

4008

mchunkptr next = chunk_plus_offset(oldp, oldsize);

4009

mchunkptr newp = 0;

4010

void* extra = 0;

4011

4012

/* Try to either shrink or extend into top. Else malloc-copy-free */

4013

4014

if (RTCHECK(ok_address(m, oldp) && ok_cinuse(oldp) &&

4015

ok_next(oldp, next) && ok_pinuse(next))) {

4016

size_t nb = request2size(bytes);

4017

if (is_mmapped(oldp))

4018

newp = mmap_resize(m, oldp, nb);

4019

else if (oldsize >= nb) { /* already big enough */

4020

size_t rsize = oldsize - nb;

4021

newp = oldp;

4022

if (rsize >= MIN_CHUNK_SIZE) {

4023

mchunkptr remainder = chunk_plus_offset(newp, nb);

4024

set_inuse(m, newp, nb);

4025

set_inuse(m, remainder, rsize);

4026

extra = chunk2mem(remainder);

4027

}

4028

}

4029

else if (next == m->top && oldsize + m->topsize > nb) {

4030

/* Expand into top */

4031

size_t newsize = oldsize + m->topsize;

4032

size_t newtopsize = newsize - nb;

4033

mchunkptr newtop = chunk_plus_offset(oldp, nb);

4034

set_inuse(m, oldp, nb);

4035

newtop->head = newtopsize |PINUSE_BIT;

4036

m->top = newtop;

4037

m->topsize = newtopsize;

4038

newp = oldp;

4039

}

4040

}

4041

else {

4042

USAGE_ERROR_ACTION(m, oldmem);

4043

POSTACTION(m);

4044

return 0;

4045

}

4046

4047

POSTACTION(m);

4048

4049

if (newp != 0) {

4050

if (extra != 0) {

4051

internal_free(m, extra);

4052

}

4053

check_inuse_chunk(m, newp);

4054

return chunk2mem(newp);

4055

}

4056

else {

4057

void* newmem = internal_malloc(m, bytes);

4058

if (newmem != 0) {

4059

size_t oc = oldsize - overhead_for(oldp);

4060

memcpy(newmem, oldmem, (oc < bytes)? oc : bytes);

4061

internal_free(m, oldmem);

4062

}

4063

return newmem;

4064

}

4065

}

4066

return 0;

4067

}

4068

4069

/* --------------------------- memalign support -------------------------- */

4070

4071

static void* internal_memalign(mstate m, size_t alignment, size_t bytes) {

4072

if (alignment <= MALLOC_ALIGNMENT) /* Can just use malloc */

4073

return internal_malloc(m, bytes);

4074

if (alignment < MIN_CHUNK_SIZE) /* must be at least a minimum chunk size */

4075

alignment = MIN_CHUNK_SIZE;

4076

if ((alignment & (alignment-SIZE_T_ONE)) != 0) {/* Ensure a power of 2 */

4077

size_t a = MALLOC_ALIGNMENT << 1;

4078

while (a < alignment) a <<= 1;

4079

alignment = a;

4080

}

4081

4082

if (bytes >= MAX_REQUEST - alignment) {

4083

if (m != 0) { /* Test isn't needed but avoids compiler warning */

4084

MALLOC_FAILURE_ACTION;

4085

}

4086

}

4087

else {

4088

size_t nb = request2size(bytes);

4089

size_t req = nb + alignment + MIN_CHUNK_SIZE - CHUNK_OVERHEAD;

4090

char* mem = (char*)internal_malloc(m, req);

4091

if (mem != 0) {

4092

void* leader = 0;

4093

void* trailer = 0;

4094

mchunkptr p = mem2chunk(mem);

4095

4096

if (PREACTION(m)) return 0;

4097

if ((((size_t)(mem)) % alignment) != 0) { /* misaligned */

4098

/*

4099

Find an aligned spot inside chunk. Since we need to give

4100

back leading space in a chunk of at least MIN_CHUNK_SIZE, if

4101

the first calculation places us at a spot with less than

4102

MIN_CHUNK_SIZE leader, we can move to the next aligned spot.

4103

We've allocated enough total room so that this is always

4104

possible.

4105

*/

4106

char* br = (char*)mem2chunk((size_t)(((size_t)(mem +

4107

alignment -

4108

SIZE_T_ONE)) &

4109

-alignment));

4110

char* pos = ((size_t)(br - (char*)(p)) >= MIN_CHUNK_SIZE)?

4111

br : br+alignment;

4112

mchunkptr newp = (mchunkptr)pos;

4113

size_t leadsize = pos - (char*)(p);

4114

size_t newsize = chunksize(p) - leadsize;

4115

4116

if (is_mmapped(p)) { /* For mmapped chunks, just adjust offset */

4117

newp->prev_foot = p->prev_foot + leadsize;

4118

newp->head = (newsize|CINUSE_BIT);

4119

}

4120

else { /* Otherwise, give back leader, use the rest */

4121

set_inuse(m, newp, newsize);

4122

set_inuse(m, p, leadsize);

4123

leader = chunk2mem(p);

4124

}

4125

p = newp;

4126

}

4127

4128

/* Give back spare room at the end */

4129

if (!is_mmapped(p)) {

4130

size_t size = chunksize(p);

4131

if (size > nb + MIN_CHUNK_SIZE) {

4132

size_t remainder_size = size - nb;

4133

mchunkptr remainder = chunk_plus_offset(p, nb);

4134

set_inuse(m, p, nb);

4135

set_inuse(m, remainder, remainder_size);

4136

trailer = chunk2mem(remainder);

4137

}

4138

}

4139

4140

assert (chunksize(p) >= nb);

4141

assert((((size_t)(chunk2mem(p))) % alignment) == 0);

4142

check_inuse_chunk(m, p);

4143

POSTACTION(m);

4144

if (leader != 0) {

4145

internal_free(m, leader);

4146

}

4147

if (trailer != 0) {

4148

internal_free(m, trailer);

4149

}

4150

return chunk2mem(p);

4151

}

4152

}

4153

return 0;

4154

}

4155

4156

/* ------------------------ comalloc/coalloc support --------------------- */

4157

4158

static void** ialloc(mstate m,

4159

size_t n_elements,

4160

size_t* sizes,

4161

int opts,

4162

void* chunks[]) {

4163

/*

4164

This provides common support for independent_X routines, handling

4165

all of the combinations that can result.

4166

4167

The opts arg has:

4168

bit 0 set if all elements are same size (using sizes[0])

4169

bit 1 set if elements should be zeroed

4170

*/

4171

4172

size_t element_size; /* chunksize of each element, if all same */

4173

size_t contents_size; /* total size of elements */

4174

size_t array_size; /* request size of pointer array */

4175

void* mem; /* malloced aggregate space */

4176

mchunkptr p; /* corresponding chunk */

4177

size_t remainder_size; /* remaining bytes while splitting */

4178

void** marray; /* either "chunks" or malloced ptr array */

4179

mchunkptr array_chunk; /* chunk for malloced ptr array */

4180

flag_t was_enabled; /* to disable mmap */

4181

size_t size;

4182

size_t i;

4183

4184

/* compute array length, if needed */

4185

if (chunks != 0) {

4186

if (n_elements == 0)

4187

return chunks; /* nothing to do */

4188

marray = chunks;

4189

array_size = 0;

4190

}

4191

else {

4192

/* if empty req, must still return chunk representing empty array */

4193

if (n_elements == 0)

4194

return (void**)internal_malloc(m, 0);

4195

marray = 0;

4196

array_size = request2size(n_elements * (sizeof(void*)));

4197

}

4198

4199

/* compute total element size */

4200

if (opts & 0x1) { /* all-same-size */

4201

element_size = request2size(*sizes);

4202

contents_size = n_elements * element_size;

4203

}

4204

else { /* add up all the sizes */

4205

element_size = 0;

4206

contents_size = 0;

4207

for (i = 0; i != n_elements; ++i)

4208

contents_size += request2size(sizes[i]);

4209

}

4210

4211

size = contents_size + array_size;

4212

4213

/*

4214

Allocate the aggregate chunk. First disable direct-mmapping so

4215

malloc won't use it, since we would not be able to later

4216

free/realloc space internal to a segregated mmap region.

4217

*/

4218

was_enabled = use_mmap(m);

4219

disable_mmap(m);

4220

mem = internal_malloc(m, size - CHUNK_OVERHEAD);

4221

if (was_enabled)

4222

enable_mmap(m);

4223

if (mem == 0)

4224

return 0;

4225

4226

if (PREACTION(m)) return 0;

4227

p = mem2chunk(mem);

4228

remainder_size = chunksize(p);

4229

4230

assert(!is_mmapped(p));

4231

4232

if (opts & 0x2) { /* optionally clear the elements */

4233

memset((size_t*)mem, 0, remainder_size - SIZE_T_SIZE - array_size);

4234

}

4235

4236

/* If not provided, allocate the pointer array as final part of chunk */

4237

if (marray == 0) {

4238

size_t array_chunk_size;

4239

array_chunk = chunk_plus_offset(p, contents_size);

4240

array_chunk_size = remainder_size - contents_size;

4241

marray = (void**) (chunk2mem(array_chunk));

4242

set_size_and_pinuse_of_inuse_chunk(m, array_chunk, array_chunk_size);

4243

remainder_size = contents_size;

4244

}

4245

4246

/* split out elements */

4247

for (i = 0; ; ++i) {

4248

marray[i] = chunk2mem(p);

4249

if (i != n_elements-1) {

4250

if (element_size != 0)

4251

size = element_size;

4252

else

4253

size = request2size(sizes[i]);

4254

remainder_size -= size;

4255

set_size_and_pinuse_of_inuse_chunk(m, p, size);

4256

p = chunk_plus_offset(p, size);

4257

}

4258

else { /* the final element absorbs any overallocation slop */

4259

set_size_and_pinuse_of_inuse_chunk(m, p, remainder_size);

4260

break;

4261

}

4262

}

4263

4264

#if DEBUG

4265

if (marray != chunks) {

4266

/* final element must have exactly exhausted chunk */

4267

if (element_size != 0) {

4268

assert(remainder_size == element_size);

4269

}

4270

else {

4271

assert(remainder_size == request2size(sizes[i]));

4272

}

4273

check_inuse_chunk(m, mem2chunk(marray));

4274

}

4275

for (i = 0; i != n_elements; ++i)

4276

check_inuse_chunk(m, mem2chunk(marray[i]));

4277

4278

#endif /* DEBUG */

4279

4280

POSTACTION(m);

4281

return marray;

4282

}

4283

4284

4285

/* -------------------------- public routines ---------------------------- */

4286

4287

#if !ONLY_MSPACES

4288

4289

void* dlmalloc(size_t bytes) {

4290

/*

4291

Basic algorithm:

4292

If a small request (< 256 bytes minus per-chunk overhead):

4293

1. If one exists, use a remainderless chunk in associated smallbin.

4294

(Remainderless means that there are too few excess bytes to

4295

represent as a chunk.)

4296

2. If it is big enough, use the dv chunk, which is normally the

4297

chunk adjacent to the one used for the most recent small request.

4298

3. If one exists, split the smallest available chunk in a bin,

4299

saving remainder in dv.

4300

4. If it is big enough, use the top chunk.

4301

5. If available, get memory from system and use it

4302

Otherwise, for a large request:

4303

1. Find the smallest available binned chunk that fits, and use it

4304

if it is better fitting than dv chunk, splitting if necessary.

4305

2. If better fitting than any binned chunk, use the dv chunk.

4306

3. If it is big enough, use the top chunk.

4307

4. If request size >= mmap threshold, try to directly mmap this chunk.

4308

5. If available, get memory from system and use it

4309

4310

The ugly goto's here ensure that postaction occurs along all paths.

4311

*/

4312

4313

if (!PREACTION(gm)) {

4314

void* mem;

4315

size_t nb;

4316

if (bytes <= MAX_SMALL_REQUEST) {

4317

bindex_t idx;

4318

binmap_t smallbits;

4319

nb = (bytes < MIN_REQUEST)? MIN_CHUNK_SIZE : pad_request(bytes);

4320

idx = small_index(nb);

4321

smallbits = gm->smallmap >> idx;

4322

4323

if ((smallbits & 0x3U) != 0) { /* Remainderless fit to a smallbin. */

4324

mchunkptr b, p;

4325

idx += ~smallbits & 1; /* Uses next bin if idx empty */

4326

b = smallbin_at(gm, idx);

4327

p = b->fd;

4328

assert(chunksize(p) == small_index2size(idx));

4329

unlink_first_small_chunk(gm, b, p, idx);

4330

set_inuse_and_pinuse(gm, p, small_index2size(idx));

4331

mem = chunk2mem(p);

4332

check_malloced_chunk(gm, mem, nb);

4333

goto postaction;

4334

}

4335

4336

else if (nb > gm->dvsize) {

4337

if (smallbits != 0) { /* Use chunk in next nonempty smallbin */

4338

mchunkptr b, p, r;

4339

size_t rsize;

4340

bindex_t i;

4341

binmap_t leftbits = (smallbits << idx) & left_bits(idx2bit(idx));

4342

binmap_t leastbit = least_bit(leftbits);

4343

compute_bit2idx(leastbit, i);

4344

b = smallbin_at(gm, i);

4345

p = b->fd;

4346

assert(chunksize(p) == small_index2size(i));

4347

unlink_first_small_chunk(gm, b, p, i);

4348

rsize = small_index2size(i) - nb;

4349

/* Fit here cannot be remainderless if 4byte sizes */

4350

if (SIZE_T_SIZE != 4 && rsize < MIN_CHUNK_SIZE)

4351

set_inuse_and_pinuse(gm, p, small_index2size(i));

4352

else {

4353

set_size_and_pinuse_of_inuse_chunk(gm, p, nb);

4354

r = chunk_plus_offset(p, nb);

4355

set_size_and_pinuse_of_free_chunk(r, rsize);

4356

replace_dv(gm, r, rsize);

4357

}

4358

mem = chunk2mem(p);

4359

check_malloced_chunk(gm, mem, nb);

4360

goto postaction;

4361

}

4362

4363

else if (gm->treemap != 0 && (mem = tmalloc_small(gm, nb)) != 0) {

4364

check_malloced_chunk(gm, mem, nb);

4365

goto postaction;

4366

}

4367

}

4368

}

4369

else if (bytes >= MAX_REQUEST)

4370

nb = MAX_SIZE_T; /* Too big to allocate. Force failure (in sys alloc) */

4371

else {

4372

nb = pad_request(bytes);

4373

if (gm->treemap != 0 && (mem = tmalloc_large(gm, nb)) != 0) {

4374

check_malloced_chunk(gm, mem, nb);

4375

goto postaction;

4376

}

4377

}

4378

4379

if (nb <= gm->dvsize) {

4380

size_t rsize = gm->dvsize - nb;

4381

mchunkptr p = gm->dv;

4382

if (rsize >= MIN_CHUNK_SIZE) { /* split dv */

4383

mchunkptr r = gm->dv = chunk_plus_offset(p, nb);

4384

gm->dvsize = rsize;

4385

set_size_and_pinuse_of_free_chunk(r, rsize);

4386

set_size_and_pinuse_of_inuse_chunk(gm, p, nb);

4387

}

4388

else { /* exhaust dv */

4389

size_t dvs = gm->dvsize;

4390

gm->dvsize = 0;

4391

gm->dv = 0;

4392

set_inuse_and_pinuse(gm, p, dvs);

4393

}

4394

mem = chunk2mem(p);

4395

check_malloced_chunk(gm, mem, nb);

4396

goto postaction;

4397

}

4398

4399

else if (nb < gm->topsize) { /* Split top */

4400

size_t rsize = gm->topsize -= nb;

4401

mchunkptr p = gm->top;

4402

mchunkptr r = gm->top = chunk_plus_offset(p, nb);

4403

r->head = rsize | PINUSE_BIT;

4404

set_size_and_pinuse_of_inuse_chunk(gm, p, nb);

4405

mem = chunk2mem(p);

4406

check_top_chunk(gm, gm->top);

4407

check_malloced_chunk(gm, mem, nb);

4408

goto postaction;

4409

}

4410

4411

mem = sys_alloc(gm, nb);

4412

4413

postaction:

4414

POSTACTION(gm);

4415

return mem;

4416

}

4417

4418

return 0;

4419

}

4420

4421

void dlfree(void* mem) {

4422

/*

4423

Consolidate freed chunks with preceeding or succeeding bordering

4424

free chunks, if they exist, and then place in a bin. Intermixed

4425

with special cases for top, dv, mmapped chunks, and usage errors.

4426

*/

4427

4428

if (mem != 0) {

4429

mchunkptr p = mem2chunk(mem);

4430

#if FOOTERS

4431

mstate fm = get_mstate_for(p);

4432

if (!ok_magic(fm)) {

4433

USAGE_ERROR_ACTION(fm, p);

4434

return;

4435

}

4436

#else /* FOOTERS */

4437

#define fm gm

4438

#endif /* FOOTERS */

4439

if (!PREACTION(fm)) {

4440

check_inuse_chunk(fm, p);

4441

if (RTCHECK(ok_address(fm, p) && ok_cinuse(p))) {

4442

size_t psize = chunksize(p);

4443

mchunkptr next = chunk_plus_offset(p, psize);

4444

if (!pinuse(p)) {

4445

size_t prevsize = p->prev_foot;

4446

if ((prevsize & IS_MMAPPED_BIT) != 0) {

4447

prevsize &= ~IS_MMAPPED_BIT;

4448

psize += prevsize + MMAP_FOOT_PAD;

4449

if (CALL_MUNMAP((char*)p - prevsize, psize) == 0)

4450

fm->footprint -= psize;

4451

goto postaction;

4452

}

4453

else {

4454

mchunkptr prev = chunk_minus_offset(p, prevsize);

4455

psize += prevsize;

4456

p = prev;

4457

if (RTCHECK(ok_address(fm, prev))) { /* consolidate backward */

4458

if (p != fm->dv) {

4459

unlink_chunk(fm, p, prevsize);

4460

}

4461

else if ((next->head & INUSE_BITS) == INUSE_BITS) {

4462

fm->dvsize = psize;

4463

set_free_with_pinuse(p, psize, next);

4464

goto postaction;

4465

}

4466

}

4467

else

4468

goto erroraction;

4469

}

4470

}

4471

4472

if (RTCHECK(ok_next(p, next) && ok_pinuse(next))) {

4473

if (!cinuse(next)) { /* consolidate forward */

4474

if (next == fm->top) {

4475

size_t tsize = fm->topsize += psize;

4476

fm->top = p;

4477

p->head = tsize | PINUSE_BIT;

4478

if (p == fm->dv) {

4479

fm->dv = 0;

4480

fm->dvsize = 0;

4481

}

4482

if (should_trim(fm, tsize))

4483

sys_trim(fm, 0);

4484

goto postaction;

4485

}

4486

else if (next == fm->dv) {

4487

size_t dsize = fm->dvsize += psize;

4488

fm->dv = p;

4489

set_size_and_pinuse_of_free_chunk(p, dsize);

4490

goto postaction;

4491

}

4492

else {

4493

size_t nsize = chunksize(next);

4494

psize += nsize;

4495

unlink_chunk(fm, next, nsize);

4496

set_size_and_pinuse_of_free_chunk(p, psize);

4497

if (p == fm->dv) {

4498

fm->dvsize = psize;

4499

goto postaction;

4500

}

4501

}

4502

}

4503

else

4504

set_free_with_pinuse(p, psize, next);

4505

insert_chunk(fm, p, psize);

4506

check_free_chunk(fm, p);

4507

goto postaction;

4508

}

4509

}

4510

erroraction:

4511

USAGE_ERROR_ACTION(fm, p);

4512

postaction:

4513

POSTACTION(fm);

4514

}

4515

}

4516

#if !FOOTERS

4517

#undef fm

4518

#endif /* FOOTERS */

4519

}

4520

4521

void* dlcalloc(size_t n_elements, size_t elem_size) {

4522

void* mem;

4523

size_t req = 0;

4524

if (n_elements != 0) {

4525

req = n_elements * elem_size;

4526

if (((n_elements | elem_size) & ~(size_t)0xffff) &&

4527

(req / n_elements != elem_size))

4528

req = MAX_SIZE_T; /* force downstream failure on overflow */

4529

}

4530

mem = dlmalloc(req);

4531

if (mem != 0 && calloc_must_clear(mem2chunk(mem)))

4532

memset(mem, 0, req);

4533

return mem;

4534

}

4535

4536

void* dlrealloc(void* oldmem, size_t bytes) {

4537

if (oldmem == 0)

4538

return dlmalloc(bytes);

4539

#ifdef REALLOC_ZERO_BYTES_FREES

4540

if (bytes == 0) {

4541

dlfree(oldmem);

4542

return 0;

4543

}

4544

#endif /* REALLOC_ZERO_BYTES_FREES */

4545

else {

4546

#if ! FOOTERS

4547

mstate m = gm;

4548

#else /* FOOTERS */

4549

mstate m = get_mstate_for(mem2chunk(oldmem));

4550

if (!ok_magic(m)) {

4551

USAGE_ERROR_ACTION(m, oldmem);

4552

return 0;

4553

}

4554

#endif /* FOOTERS */

4555

return internal_realloc(m, oldmem, bytes);

4556

}

4557

}

4558

4559

void* dlmemalign(size_t alignment, size_t bytes) {

4560

return internal_memalign(gm, alignment, bytes);

4561

}

4562

4563

void** dlindependent_calloc(size_t n_elements, size_t elem_size,

4564

void* chunks[]) {

4565

size_t sz = elem_size; /* serves as 1-element array */

4566

return ialloc(gm, n_elements, &sz, 3, chunks);

4567

}

4568

4569

void** dlindependent_comalloc(size_t n_elements, size_t sizes[],

4570

void* chunks[]) {

4571

return ialloc(gm, n_elements, sizes, 0, chunks);

4572

}

4573

4574

void* dlvalloc(size_t bytes) {

4575

size_t pagesz;

4576

init_mparams();

4577

pagesz = mparams.page_size;

4578

return dlmemalign(pagesz, bytes);

4579

}

4580

4581

void* dlpvalloc(size_t bytes) {

4582

size_t pagesz;

4583

init_mparams();

4584

pagesz = mparams.page_size;

4585

return dlmemalign(pagesz, (bytes + pagesz - SIZE_T_ONE) & ~(pagesz - SIZE_T_ONE));

4586

}

4587

4588

int dlmalloc_trim(size_t pad) {

4589

int result = 0;

4590

if (!PREACTION(gm)) {

4591

result = sys_trim(gm, pad);

4592

POSTACTION(gm);

4593

}

4594

return result;

4595

}

4596

4597

size_t dlmalloc_footprint(void) {

4598

return gm->footprint;

4599

}

4600

4601

size_t dlmalloc_max_footprint(void) {

4602

return gm->max_footprint;

4603

}

4604

4605

#if !NO_MALLINFO

4606

struct mallinfo dlmallinfo(void) {

4607

return internal_mallinfo(gm);

4608

}

4609

#endif /* NO_MALLINFO */

4610

4611

void dlmalloc_stats() {

4612

internal_malloc_stats(gm);

4613

}

4614

4615

size_t dlmalloc_usable_size(void* mem) {

4616

if (mem != 0) {

4617

mchunkptr p = mem2chunk(mem);

4618

if (cinuse(p))

4619

return chunksize(p) - overhead_for(p);

4620

}

4621

return 0;

4622

}

4623

4624

int dlmallopt(int param_number, int value) {

4625

return change_mparam(param_number, value);

4626

}

4627

4628

#endif /* !ONLY_MSPACES */

4629

4630

/* ----------------------------- user mspaces ---------------------------- */

4631

4632

#if MSPACES

4633

4634

static mstate init_user_mstate(char* tbase, size_t tsize) {

4635

size_t msize = pad_request(sizeof(struct malloc_state));

4636

mchunkptr mn;

4637

mchunkptr msp = align_as_chunk(tbase);

4638

mstate m = (mstate)(chunk2mem(msp));

4639

memset(m, 0, msize);

4640

INITIAL_LOCK(&m->mutex);

4641

msp->head = (msize|PINUSE_BIT|CINUSE_BIT);

4642

m->seg.base = m->least_addr = tbase;

4643

m->seg.size = m->footprint = m->max_footprint = tsize;

4644

m->magic = mparams.magic;

4645

m->mflags = mparams.default_mflags;

4646

m->nedpool = 0;

4647

disable_contiguous(m);

4648

init_bins(m);

4649

mn = next_chunk(mem2chunk(m));

4650

init_top(m, mn, (size_t)((tbase + tsize) - (char*)mn) - TOP_FOOT_SIZE);

4651

check_top_chunk(m, m->top);

4652

return m;

4653

}

4654

4655

mspace create_mspace(size_t capacity, int locked) {

4656

mstate m = 0;

4657

size_t msize = pad_request(sizeof(struct malloc_state));

4658

init_mparams(); /* Ensure pagesize etc initialized */

4659

4660

if (capacity < (size_t) -(msize + TOP_FOOT_SIZE + mparams.page_size)) {

4661

size_t rs = ((capacity == 0)? mparams.granularity :

4662

(capacity + TOP_FOOT_SIZE + msize));

4663

size_t tsize = granularity_align(rs);

4664

char* tbase = (char*)(CALL_MMAP(tsize));

4665

if (tbase != CMFAIL) {

4666

m = init_user_mstate(tbase, tsize);

4667

m->seg.sflags = IS_MMAPPED_BIT;

4668

set_lock(m, locked);

4669

}

4670

}

4671

return (mspace)m;

4672

}

4673

4674

mspace create_mspace_with_base(void* base, size_t capacity, int locked) {

4675

mstate m = 0;

4676

size_t msize = pad_request(sizeof(struct malloc_state));

4677

init_mparams(); /* Ensure pagesize etc initialized */

4678

4679

if (capacity > msize + TOP_FOOT_SIZE &&

4680

capacity < (size_t) -(msize + TOP_FOOT_SIZE + mparams.page_size)) {

4681

m = init_user_mstate((char*)base, capacity);

4682

m->seg.sflags = EXTERN_BIT;

4683

set_lock(m, locked);

4684

}

4685

return (mspace)m;

4686

}

4687

4688

size_t destroy_mspace(mspace msp) {

4689

size_t freed = 0;

4690

mstate ms = (mstate)msp;

4691

if (ok_magic(ms)) {

4692

msegmentptr sp = &ms->seg;

4693

while (sp != 0) {

4694

char* base = sp->base;

4695

size_t size = sp->size;

4696

flag_t flag = sp->sflags;

4697

sp = sp->next;

4698

if ((flag & IS_MMAPPED_BIT) && !(flag & EXTERN_BIT) &&

4699

CALL_MUNMAP(base, size) == 0)

4700

freed += size;

4701

}

4702

}

4703

else {

4704

USAGE_ERROR_ACTION(ms,ms);

4705

}

4706

return freed;

4707

}

4708

4709

/*

4710

mspace versions of routines are near-clones of the global

4711

versions. This is not so nice but better than the alternatives.

4712

*/

4713

4714

4715

void* mspace_malloc(mspace msp, size_t bytes) {

4716

mstate ms = (mstate)msp;

4717

if (!ok_magic(ms)) {

4718

USAGE_ERROR_ACTION(ms,ms);

4719

return 0;

4720

}

4721

if (!PREACTION(ms)) {

4722

void* mem;

4723

size_t nb;

4724

if (bytes <= MAX_SMALL_REQUEST) {

4725

bindex_t idx;

4726

binmap_t smallbits;

4727

nb = (bytes < MIN_REQUEST)? MIN_CHUNK_SIZE : pad_request(bytes);

4728

idx = small_index(nb);

4729

smallbits = ms->smallmap >> idx;

4730

4731

if ((smallbits & 0x3U) != 0) { /* Remainderless fit to a smallbin. */

4732

mchunkptr b, p;

4733

idx += ~smallbits & 1; /* Uses next bin if idx empty */

4734

b = smallbin_at(ms, idx);

4735

p = b->fd;

4736

assert(chunksize(p) == small_index2size(idx));

4737

unlink_first_small_chunk(ms, b, p, idx);

4738

set_inuse_and_pinuse(ms, p, small_index2size(idx));

4739

mem = chunk2mem(p);

4740

check_malloced_chunk(ms, mem, nb);

4741

goto postaction;

4742

}

4743

4744

else if (nb > ms->dvsize) {

4745

if (smallbits != 0) { /* Use chunk in next nonempty smallbin */

4746

mchunkptr b, p, r;

4747

size_t rsize;

4748

bindex_t i;

4749

binmap_t leftbits = (smallbits << idx) & left_bits(idx2bit(idx));

4750

binmap_t leastbit = least_bit(leftbits);

4751

compute_bit2idx(leastbit, i);

4752

b = smallbin_at(ms, i);

4753

p = b->fd;

4754

assert(chunksize(p) == small_index2size(i));

4755

unlink_first_small_chunk(ms, b, p, i);

4756

rsize = small_index2size(i) - nb;

4757

/* Fit here cannot be remainderless if 4byte sizes */

4758

if (SIZE_T_SIZE != 4 && rsize < MIN_CHUNK_SIZE)

4759

set_inuse_and_pinuse(ms, p, small_index2size(i));

4760

else {

4761

set_size_and_pinuse_of_inuse_chunk(ms, p, nb);

4762

r = chunk_plus_offset(p, nb);

4763

set_size_and_pinuse_of_free_chunk(r, rsize);

4764

replace_dv(ms, r, rsize);

4765

}

4766

mem = chunk2mem(p);

4767

check_malloced_chunk(ms, mem, nb);

4768

goto postaction;

4769

}

4770

4771

else if (ms->treemap != 0 && (mem = tmalloc_small(ms, nb)) != 0) {

4772

check_malloced_chunk(ms, mem, nb);

4773

goto postaction;

4774

}

4775

}

4776

}

4777

else if (bytes >= MAX_REQUEST)

4778

nb = MAX_SIZE_T; /* Too big to allocate. Force failure (in sys alloc) */

4779

else {

4780

nb = pad_request(bytes);

4781

if (ms->treemap != 0 && (mem = tmalloc_large(ms, nb)) != 0) {

4782

check_malloced_chunk(ms, mem, nb);

4783

goto postaction;

4784

}

4785

}

4786

4787

if (nb <= ms->dvsize) {

4788

size_t rsize = ms->dvsize - nb;

4789

mchunkptr p = ms->dv;

4790

if (rsize >= MIN_CHUNK_SIZE) { /* split dv */

4791

mchunkptr r = ms->dv = chunk_plus_offset(p, nb);

4792

ms->dvsize = rsize;

4793

set_size_and_pinuse_of_free_chunk(r, rsize);

4794

set_size_and_pinuse_of_inuse_chunk(ms, p, nb);

4795

}

4796

else { /* exhaust dv */

4797

size_t dvs = ms->dvsize;

4798

ms->dvsize = 0;

4799

ms->dv = 0;

4800

set_inuse_and_pinuse(ms, p, dvs);

4801

}

4802

mem = chunk2mem(p);

4803

check_malloced_chunk(ms, mem, nb);

4804

goto postaction;

4805

}

4806

4807

else if (nb < ms->topsize) { /* Split top */

4808

size_t rsize = ms->topsize -= nb;

4809

mchunkptr p = ms->top;

4810

mchunkptr r = ms->top = chunk_plus_offset(p, nb);

4811

r->head = rsize | PINUSE_BIT;

4812

set_size_and_pinuse_of_inuse_chunk(ms, p, nb);

4813

mem = chunk2mem(p);

4814

check_top_chunk(ms, ms->top);

4815

check_malloced_chunk(ms, mem, nb);

4816

goto postaction;

4817

}

4818

4819

mem = sys_alloc(ms, nb);

4820

4821

postaction:

4822

POSTACTION(ms);

4823

return mem;

4824

}

4825

4826

return 0;

4827

}

4828

4829

void mspace_free(mspace msp, void* mem) {

4830

if (mem != 0) {

4831

mchunkptr p = mem2chunk(mem);

4832

#if FOOTERS

4833

mstate fm = get_mstate_for(p);

4834

#else /* FOOTERS */

4835

mstate fm = (mstate)msp;

4836

#endif /* FOOTERS */

4837

if (!ok_magic(fm)) {

4838

USAGE_ERROR_ACTION(fm, p);

4839

return;

4840

}

4841

if (!PREACTION(fm)) {

4842

check_inuse_chunk(fm, p);

4843

if (RTCHECK(ok_address(fm, p) && ok_cinuse(p))) {

4844

size_t psize = chunksize(p);

4845

mchunkptr next = chunk_plus_offset(p, psize);

4846

if (!pinuse(p)) {

4847

size_t prevsize = p->prev_foot;

4848

if ((prevsize & IS_MMAPPED_BIT) != 0) {

4849

prevsize &= ~IS_MMAPPED_BIT;

4850

psize += prevsize + MMAP_FOOT_PAD;

4851

if (CALL_MUNMAP((char*)p - prevsize, psize) == 0)

4852

fm->footprint -= psize;

4853

goto postaction;

4854

}

4855

else {

4856

mchunkptr prev = chunk_minus_offset(p, prevsize);

4857

psize += prevsize;

4858

p = prev;

4859

if (RTCHECK(ok_address(fm, prev))) { /* consolidate backward */

4860

if (p != fm->dv) {

4861

unlink_chunk(fm, p, prevsize);

4862

}

4863

else if ((next->head & INUSE_BITS) == INUSE_BITS) {

4864

fm->dvsize = psize;

4865

set_free_with_pinuse(p, psize, next);

4866

goto postaction;

4867

}

4868

}

4869

else

4870

goto erroraction;

4871

}

4872

}

4873

4874

if (RTCHECK(ok_next(p, next) && ok_pinuse(next))) {

4875

if (!cinuse(next)) { /* consolidate forward */

4876

if (next == fm->top) {

4877

size_t tsize = fm->topsize += psize;

4878

fm->top = p;

4879

p->head = tsize | PINUSE_BIT;

4880

if (p == fm->dv) {

4881

fm->dv = 0;

4882

fm->dvsize = 0;

4883

}

4884

if (should_trim(fm, tsize))

4885

sys_trim(fm, 0);

4886

goto postaction;

4887

}

4888

else if (next == fm->dv) {

4889

size_t dsize = fm->dvsize += psize;

4890

fm->dv = p;

4891

set_size_and_pinuse_of_free_chunk(p, dsize);

4892

goto postaction;

4893

}

4894

else {

4895

size_t nsize = chunksize(next);

4896

psize += nsize;

4897

unlink_chunk(fm, next, nsize);

4898

set_size_and_pinuse_of_free_chunk(p, psize);

4899

if (p == fm->dv) {

4900

fm->dvsize = psize;

4901

goto postaction;

4902

}

4903

}

4904

}

4905

else

4906

set_free_with_pinuse(p, psize, next);

4907

insert_chunk(fm, p, psize);

4908

check_free_chunk(fm, p);

4909

goto postaction;

4910

}

4911

}

4912

erroraction:

4913

USAGE_ERROR_ACTION(fm, p);

4914

postaction:

4915

POSTACTION(fm);

4916

}

4917

}

4918

}

4919

4920

void* mspace_calloc(mspace msp, size_t n_elements, size_t elem_size) {

4921

void* mem;

4922

size_t req = 0;

4923

mstate ms = (mstate)msp;

4924

if (!ok_magic(ms)) {

4925

USAGE_ERROR_ACTION(ms,ms);

4926

return 0;

4927

}

4928

if (n_elements != 0) {

4929

req = n_elements * elem_size;

4930

if (((n_elements | elem_size) & ~(size_t)0xffff) &&

4931

(req / n_elements != elem_size))

4932

req = MAX_SIZE_T; /* force downstream failure on overflow */

4933

}

4934

mem = internal_malloc(ms, req);

4935

if (mem != 0 && calloc_must_clear(mem2chunk(mem)))

4936

memset(mem, 0, req);

4937

return mem;

4938

}

4939

4940

void* mspace_realloc(mspace msp, void* oldmem, size_t bytes) {

4941

if (oldmem == 0)

4942

return mspace_malloc(msp, bytes);

4943

#ifdef REALLOC_ZERO_BYTES_FREES

4944

if (bytes == 0) {

4945

mspace_free(msp, oldmem);

4946

return 0;

4947

}

4948

#endif /* REALLOC_ZERO_BYTES_FREES */

4949

else {

4950

#if FOOTERS

4951

mchunkptr p = mem2chunk(oldmem);

4952

mstate ms = get_mstate_for(p);

4953

#else /* FOOTERS */

4954

mstate ms = (mstate)msp;

4955

#endif /* FOOTERS */

4956

if (!ok_magic(ms)) {

4957

USAGE_ERROR_ACTION(ms,ms);

4958

return 0;

4959

}

4960

return internal_realloc(ms, oldmem, bytes);

4961

}

4962

}

4963

4964

void* mspace_memalign(mspace msp, size_t alignment, size_t bytes) {

4965

mstate ms = (mstate)msp;

4966

if (!ok_magic(ms)) {

4967

USAGE_ERROR_ACTION(ms,ms);

4968

return 0;

4969

}

4970

return internal_memalign(ms, alignment, bytes);

4971

}

4972

4973

void** mspace_independent_calloc(mspace msp, size_t n_elements,

4974

size_t elem_size, void* chunks[]) {

4975

size_t sz = elem_size; /* serves as 1-element array */

4976

mstate ms = (mstate)msp;

4977

if (!ok_magic(ms)) {

4978

USAGE_ERROR_ACTION(ms,ms);

4979

return 0;

4980

}

4981

return ialloc(ms, n_elements, &sz, 3, chunks);

4982

}

4983

4984

void** mspace_independent_comalloc(mspace msp, size_t n_elements,

4985

size_t sizes[], void* chunks[]) {

4986

mstate ms = (mstate)msp;

4987

if (!ok_magic(ms)) {

4988

USAGE_ERROR_ACTION(ms,ms);

4989

return 0;

4990

}

4991

return ialloc(ms, n_elements, sizes, 0, chunks);

4992

}

4993

4994

int mspace_trim(mspace msp, size_t pad) {

4995

int result = 0;

4996

mstate ms = (mstate)msp;

4997

if (ok_magic(ms)) {

4998

if (!PREACTION(ms)) {

4999

result = sys_trim(ms, pad);

5000

POSTACTION(ms);

5001

}

5002

}

5003

else {

5004

USAGE_ERROR_ACTION(ms,ms);

5005

}

5006

return result;

5007

}

5008

5009

void mspace_malloc_stats(mspace msp) {

5010

mstate ms = (mstate)msp;

5011

if (ok_magic(ms)) {

5012

internal_malloc_stats(ms);

5013

}

5014

else {

5015

USAGE_ERROR_ACTION(ms,ms);

5016

}

5017

}

5018

5019

size_t mspace_footprint(mspace msp) {

5020

size_t result = 0;

5021

mstate ms = (mstate)msp;

5022

if (ok_magic(ms)) {

5023

result = ms->footprint;

5024

}

5025

USAGE_ERROR_ACTION(ms,ms);

5026

return result;

5027

}

5028

5029

5030

size_t mspace_max_footprint(mspace msp) {

5031

size_t result = 0;

5032

mstate ms = (mstate)msp;

5033

if (ok_magic(ms)) {

5034

result = ms->max_footprint;

5035

}

5036

USAGE_ERROR_ACTION(ms,ms);

5037

return result;

5038

}

5039

5040

5041

#if !NO_MALLINFO

5042

struct mallinfo mspace_mallinfo(mspace msp) {

5043

mstate ms = (mstate)msp;

5044

if (!ok_magic(ms)) {

5045

USAGE_ERROR_ACTION(ms,ms);

5046

}

5047

return internal_mallinfo(ms);

5048

}

5049

#endif /* NO_MALLINFO */

5050

5051

int mspace_mallopt(int param_number, int value) {

5052

return change_mparam(param_number, value);

5053

}

5054

5055

#endif /* MSPACES */

5056

5057

/* -------------------- Alternative MORECORE functions ------------------- */

5058

5059

/*

5060

Guidelines for creating a custom version of MORECORE:

5061

5062

* For best performance, MORECORE should allocate in multiples of pagesize.

5063

* MORECORE may allocate more memory than requested. (Or even less,

5064

but this will usually result in a malloc failure.)

5065

* MORECORE must not allocate memory when given argument zero, but

5066

instead return one past the end address of memory from previous

5067

nonzero call.

5068

* For best performance, consecutive calls to MORECORE with positive

5069

arguments should return increasing addresses, indicating that

5070

space has been contiguously extended.

5071

* Even though consecutive calls to MORECORE need not return contiguous

5072

addresses, it must be OK for malloc'ed chunks to span multiple

5073

regions in those cases where they do happen to be contiguous.

5074

* MORECORE need not handle negative arguments -- it may instead

5075

just return MFAIL when given negative arguments.

5076

Negative arguments are always multiples of pagesize. MORECORE

5077

must not misinterpret negative args as large positive unsigned

5078

args. You can suppress all such calls from even occurring by defining

5079

MORECORE_CANNOT_TRIM,

5080

5081

As an example alternative MORECORE, here is a custom allocator

5082

kindly contributed for pre-OSX macOS. It uses virtually but not

5083

necessarily physically contiguous non-paged memory (locked in,

5084

present and won't get swapped out). You can use it by uncommenting

5085

this section, adding some #includes, and setting up the appropriate

5086

defines above:

5087

5088

#define MORECORE osMoreCore

5089

5090

There is also a shutdown routine that should somehow be called for

5091

cleanup upon program exit.

5092

5093

#define MAX_POOL_ENTRIES 100

5094

#define MINIMUM_MORECORE_SIZE (64 * 1024U)

5095

static int next_os_pool;

5096

void *our_os_pools[MAX_POOL_ENTRIES];

5097

5098

void *osMoreCore(int size)

5099

{

5100

void *ptr = 0;

5101

static void *sbrk_top = 0;

5102

5103

if (size > 0)

5104

{

5105

if (size < MINIMUM_MORECORE_SIZE)

5106

size = MINIMUM_MORECORE_SIZE;

5107

if (CurrentExecutionLevel() == kTaskLevel)

5108

ptr = PoolAllocateResident(size + RM_PAGE_SIZE, 0);

5109

if (ptr == 0)

5110

{

5111

return (void *) MFAIL;

5112

}

5113

// save ptrs so they can be freed during cleanup

5114

our_os_pools[next_os_pool] = ptr;

5115

next_os_pool++;

5116

ptr = (void *) ((((size_t) ptr) + RM_PAGE_MASK) & ~RM_PAGE_MASK);

5117

sbrk_top = (char *) ptr + size;

5118

return ptr;

5119

}

5120

else if (size < 0)

5121

{

5122

// we don't currently support shrink behavior

5123

return (void *) MFAIL;

5124

}

5125

else

5126

{

5127

return sbrk_top;

5128

}

5129

}

5130

5131

// cleanup any allocated memory pools

5132

// called as last thing before shutting down driver

5133

5134

void osCleanupMem(void)

5135

{

5136

void **ptr;

5137

5138

for (ptr = our_os_pools; ptr < &our_os_pools[MAX_POOL_ENTRIES]; ptr++)

5139

if (*ptr)

5140

{

5141

PoolDeallocate(*ptr);

5142

*ptr = 0;

5143

}

5144

}

5145

5146

*/

5147

5148

5149

/* -----------------------------------------------------------------------

5150

History:

5151

V2.8.3 Thu Sep 22 11:16:32 2005 Doug Lea (dl at gee)

5152

* Add max_footprint functions

5153

* Ensure all appropriate literals are size_t

5154

* Fix conditional compilation problem for some #define settings

5155

* Avoid concatenating segments with the one provided

5156

in create_mspace_with_base

5157

* Rename some variables to avoid compiler shadowing warnings

5158

* Use explicit lock initialization.

5159

* Better handling of sbrk interference.

5160

* Simplify and fix segment insertion, trimming and mspace_destroy

5161

* Reinstate REALLOC_ZERO_BYTES_FREES option from 2.7.x

5162

* Thanks especially to Dennis Flanagan for help on these.

5163

5164

V2.8.2 Sun Jun 12 16:01:10 2005 Doug Lea (dl at gee)

5165

* Fix memalign brace error.

5166

5167

V2.8.1 Wed Jun 8 16:11:46 2005 Doug Lea (dl at gee)

5168

* Fix improper #endif nesting in C++

5169

* Add explicit casts needed for C++

5170

5171

V2.8.0 Mon May 30 14:09:02 2005 Doug Lea (dl at gee)

5172

* Use trees for large bins

5173

* Support mspaces

5174

* Use segments to unify sbrk-based and mmap-based system allocation,

5175

removing need for emulation on most platforms without sbrk.

5176

* Default safety checks

5177

* Optional footer checks. Thanks to William Robertson for the idea.

5178

* Internal code refactoring

5179

* Incorporate suggestions and platform-specific changes.

5180

Thanks to Dennis Flanagan, Colin Plumb, Niall Douglas,

5181

Aaron Bachmann, Emery Berger, and others.

5182

* Speed up non-fastbin processing enough to remove fastbins.

5183

* Remove useless cfree() to avoid conflicts with other apps.

5184

* Remove internal memcpy, memset. Compilers handle builtins better.

5185

* Remove some options that no one ever used and rename others.

5186

5187

V2.7.2 Sat Aug 17 09:07:30 2002 Doug Lea (dl at gee)

5188

* Fix malloc_state bitmap array misdeclaration

5189

5190

V2.7.1 Thu Jul 25 10:58:03 2002 Doug Lea (dl at gee)

5191

* Allow tuning of FIRST_SORTED_BIN_SIZE

5192

* Use PTR_UINT as type for all ptr->int casts. Thanks to John Belmonte.

5193

* Better detection and support for non-contiguousness of MORECORE.

5194

Thanks to Andreas Mueller, Conal Walsh, and Wolfram Gloger

5195

* Bypass most of malloc if no frees. Thanks To Emery Berger.

5196

* Fix freeing of old top non-contiguous chunk im sysmalloc.

5197

* Raised default trim and map thresholds to 256K.

5198

* Fix mmap-related #defines. Thanks to Lubos Lunak.

5199

* Fix copy macros; added LACKS_FCNTL_H. Thanks to Neal Walfield.

5200

* Branch-free bin calculation

5201

* Default trim and mmap thresholds now 256K.

5202

5203

V2.7.0 Sun Mar 11 14:14:06 2001 Doug Lea (dl at gee)

5204

* Introduce independent_comalloc and independent_calloc.

5205

Thanks to Michael Pachos for motivation and help.

5206

* Make optional .h file available

5207

* Allow > 2GB requests on 32bit systems.

5208

* new WIN32 sbrk, mmap, munmap, lock code from <Walter@GeNeSys-e.de>.

5209

Thanks also to Andreas Mueller <a.mueller at paradatec.de>,

5210

and Anonymous.

5211

* Allow override of MALLOC_ALIGNMENT (Thanks to Ruud Waij for

5212

helping test this.)

5213

* memalign: check alignment arg

5214

* realloc: don't try to shift chunks backwards, since this

5215

leads to more fragmentation in some programs and doesn't

5216

seem to help in any others.

5217

* Collect all cases in malloc requiring system memory into sysmalloc

5218

* Use mmap as backup to sbrk

5219

* Place all internal state in malloc_state

5220

* Introduce fastbins (although similar to 2.5.1)

5221

* Many minor tunings and cosmetic improvements

5222

* Introduce USE_PUBLIC_MALLOC_WRAPPERS, USE_MALLOC_LOCK

5223

* Introduce MALLOC_FAILURE_ACTION, MORECORE_CONTIGUOUS

5224

Thanks to Tony E. Bennett <tbennett@nvidia.com> and others.

5225

* Include errno.h to support default failure action.

5226

5227

V2.6.6 Sun Dec 5 07:42:19 1999 Doug Lea (dl at gee)

5228

* return null for negative arguments

5229

* Added Several WIN32 cleanups from Martin C. Fong <mcfong at yahoo.com>

5230

* Add 'LACKS_SYS_PARAM_H' for those systems without 'sys/param.h'

5231

(e.g. WIN32 platforms)

5232

* Cleanup header file inclusion for WIN32 platforms

5233

* Cleanup code to avoid Microsoft Visual C++ compiler complaints

5234

* Add 'USE_DL_PREFIX' to quickly allow co-existence with existing

5235

memory allocation routines

5236

* Set 'malloc_getpagesize' for WIN32 platforms (needs more work)

5237

* Use 'assert' rather than 'ASSERT' in WIN32 code to conform to

5238

usage of 'assert' in non-WIN32 code

5239

* Improve WIN32 'sbrk()' emulation's 'findRegion()' routine to

5240

avoid infinite loop

5241

* Always call 'fREe()' rather than 'free()'

5242

5243

V2.6.5 Wed Jun 17 15:57:31 1998 Doug Lea (dl at gee)

5244

* Fixed ordering problem with boundary-stamping

5245

5246

V2.6.3 Sun May 19 08:17:58 1996 Doug Lea (dl at gee)

5247

* Added pvalloc, as recommended by H.J. Liu

5248

* Added 64bit pointer support mainly from Wolfram Gloger

5249

* Added anonymously donated WIN32 sbrk emulation

5250

* Malloc, calloc, getpagesize: add optimizations from Raymond Nijssen

5251

* malloc_extend_top: fix mask error that caused wastage after

5252

foreign sbrks

5253

* Add linux mremap support code from HJ Liu

5254

5255

V2.6.2 Tue Dec 5 06:52:55 1995 Doug Lea (dl at gee)

5256

* Integrated most documentation with the code.

5257

* Add support for mmap, with help from

5258

Wolfram Gloger (Gloger@lrz.uni-muenchen.de).

5259

* Use last_remainder in more cases.

5260

* Pack bins using idea from colin@nyx10.cs.du.edu

5261

* Use ordered bins instead of best-fit threshhold

5262

* Eliminate block-local decls to simplify tracing and debugging.

5263

* Support another case of realloc via move into top

5264

* Fix error occuring when initial sbrk_base not word-aligned.

5265

* Rely on page size for units instead of SBRK_UNIT to

5266

avoid surprises about sbrk alignment conventions.

5267

* Add mallinfo, mallopt. Thanks to Raymond Nijssen

5268

(raymond@es.ele.tue.nl) for the suggestion.

5269

* Add `pad' argument to malloc_trim and top_pad mallopt parameter.

5270

* More precautions for cases where other routines call sbrk,

5271

courtesy of Wolfram Gloger (Gloger@lrz.uni-muenchen.de).

5272

* Added macros etc., allowing use in linux libc from

5273

H.J. Lu (hjl@gnu.ai.mit.edu)

5274

* Inverted this history list

5275

5276

V2.6.1 Sat Dec 2 14:10:57 1995 Doug Lea (dl at gee)

5277

* Re-tuned and fixed to behave more nicely with V2.6.0 changes.

5278

* Removed all preallocation code since under current scheme

5279

the work required to undo bad preallocations exceeds

5280

the work saved in good cases for most test programs.

5281

* No longer use return list or unconsolidated bins since

5282

no scheme using them consistently outperforms those that don't

5283

given above changes.

5284

* Use best fit for very large chunks to prevent some worst-cases.

5285

* Added some support for debugging

5286

5287

V2.6.0 Sat Nov 4 07:05:23 1995 Doug Lea (dl at gee)

5288

* Removed footers when chunks are in use. Thanks to

5289

Paul Wilson (wilson@cs.texas.edu) for the suggestion.

5290

5291

V2.5.4 Wed Nov 1 07:54:51 1995 Doug Lea (dl at gee)

5292

* Added malloc_trim, with help from Wolfram Gloger

5293

(wmglo@Dent.MED.Uni-Muenchen.DE).

5294

5295

V2.5.3 Tue Apr 26 10:16:01 1994 Doug Lea (dl at g)

5296

5297

V2.5.2 Tue Apr 5 16:20:40 1994 Doug Lea (dl at g)

5298

* realloc: try to expand in both directions

5299

* malloc: swap order of clean-bin strategy;

5300

* realloc: only conditionally expand backwards

5301

* Try not to scavenge used bins

5302

* Use bin counts as a guide to preallocation

5303

* Occasionally bin return list chunks in first scan

5304

* Add a few optimizations from colin@nyx10.cs.du.edu

5305

5306

V2.5.1 Sat Aug 14 15:40:43 1993 Doug Lea (dl at g)

5307

* faster bin computation & slightly different binning

5308

* merged all consolidations to one part of malloc proper

5309

(eliminating old malloc_find_space & malloc_clean_bin)

5310

* Scan 2 returns chunks (not just 1)

5311

* Propagate failure in realloc if malloc returns 0

5312

* Add stuff to allow compilation on non-ANSI compilers

5313

from kpv@research.att.com

5314

5315

V2.5 Sat Aug 7 07:41:59 1993 Doug Lea (dl at g.oswego.edu)

5316

* removed potential for odd address access in prev_chunk

5317

* removed dependency on getpagesize.h

5318

* misc cosmetics and a bit more internal documentation

5319

* anticosmetics: mangled names in macros to evade debugger strangeness

5320

* tested on sparc, hp-700, dec-mips, rs6000

5321

with gcc & native cc (hp, dec only) allowing

5322

Detlefs & Zorn comparison study (in SIGPLAN Notices.)

5323

5324

Trial version Fri Aug 28 13:14:29 1992 Doug Lea (dl at g.oswego.edu)

5325

* Based loosely on libg++-1.2X malloc. (It retains some of the overall

5326

structure of old version, but most details differ.)

5327

5328

*/