alloc_engine.cc 108 KB
Newer Older
1
// Copyright (C) 2012-2015 Internet Systems Consortium, Inc. ("ISC")
2
//
3
4
5
// This Source Code Form is subject to the terms of the Mozilla Public
// License, v. 2.0. If a copy of the MPL was not distributed with this
// file, You can obtain one at http://mozilla.org/MPL/2.0/.
6

7
8
#include <config.h>

9
10
11
#include <dhcp/dhcp6.h>
#include <dhcp/pkt4.h>
#include <dhcp/pkt6.h>
12
#include <dhcp_ddns/ncr_msg.h>
13
#include <dhcpsrv/alloc_engine.h>
14
#include <dhcpsrv/alloc_engine_log.h>
15
#include <dhcpsrv/dhcpsrv_log.h>
16
#include <dhcpsrv/host_mgr.h>
17
#include <dhcpsrv/host.h>
18
#include <dhcpsrv/lease_mgr_factory.h>
19
#include <dhcpsrv/ncr_generator.h>
20
21
#include <hooks/callout_handle.h>
#include <hooks/hooks_manager.h>
22
#include <dhcpsrv/callout_handle_store.h>
23
#include <stats/stats_mgr.h>
24
#include <util/stopwatch.h>
25
26
27
#include <hooks/server_hooks.h>
#include <hooks/hooks_manager.h>

28
29
#include <boost/foreach.hpp>

30
#include <cstring>
31
#include <sstream>
32
#include <limits>
33
#include <vector>
34
#include <stdint.h>
35
#include <string.h>
36

37
using namespace isc::asiolink;
38
using namespace isc::dhcp;
39
using namespace isc::dhcp_ddns;
40
using namespace isc::hooks;
Tomek Mrugalski's avatar
Tomek Mrugalski committed
41
using namespace isc::stats;
42

43
44
45
namespace {

/// Structure that holds registered hook indexes
46
47
struct AllocEngineHooks {
    int hook_index_lease4_select_; ///< index for "lease4_receive" hook point
48
    int hook_index_lease4_renew_;  ///< index for "lease4_renew" hook point
49
    int hook_index_lease4_expire_; ///< index for "lease4_expire" hook point
50
    int hook_index_lease4_recover_;///< index for "lease4_recover" hook point
51
    int hook_index_lease6_select_; ///< index for "lease6_receive" hook point
52
53
    int hook_index_lease6_renew_;  ///< index for "lease6_renew" hook point
    int hook_index_lease6_rebind_; ///< index for "lease6_rebind" hook point
54
    int hook_index_lease6_expire_; ///< index for "lease6_expire" hook point
55
    int hook_index_lease6_recover_;///< index for "lease6_recover" hook point
56
57

    /// Constructor that registers hook points for AllocationEngine
58
    AllocEngineHooks() {
59
        hook_index_lease4_select_ = HooksManager::registerHook("lease4_select");
60
        hook_index_lease4_renew_  = HooksManager::registerHook("lease4_renew");
61
        hook_index_lease4_expire_ = HooksManager::registerHook("lease4_expire");
62
        hook_index_lease4_recover_= HooksManager::registerHook("lease4_recover");
63
        hook_index_lease6_select_ = HooksManager::registerHook("lease6_select");
64
65
66
        hook_index_lease6_renew_  = HooksManager::registerHook("lease6_renew");
        hook_index_lease6_rebind_ = HooksManager::registerHook("lease6_rebind");
        hook_index_lease6_expire_ = HooksManager::registerHook("lease6_expire");
67
        hook_index_lease6_recover_= HooksManager::registerHook("lease6_recover");
68
69
70
71
72
73
74
    }
};

// Declare a Hooks object. As this is outside any function or method, it
// will be instantiated (and the constructor run) when the module is loaded.
// As a result, the hook indexes will be defined before any method in this
// module is called.
75
AllocEngineHooks Hooks;
76
77

}; // anonymous namespace
78
79
80
81

namespace isc {
namespace dhcp {

82
AllocEngine::IterativeAllocator::IterativeAllocator(Lease::Type lease_type)
83
    :Allocator(lease_type) {
84
85
}

86
87
isc::asiolink::IOAddress
AllocEngine::IterativeAllocator::increasePrefix(const isc::asiolink::IOAddress& prefix,
Tomek Mrugalski's avatar
Tomek Mrugalski committed
88
                                                const uint8_t prefix_len) {
89
    if (!prefix.isV6()) {
90
        isc_throw(BadValue, "Prefix operations are for IPv6 only (attempted to "
91
                  "increase prefix " << prefix << ")");
92
93
94
95
96
97
98
99
100
101
    }

    // Get a buffer holding an address.
    const std::vector<uint8_t>& vec = prefix.toBytes();

    if (prefix_len < 1 || prefix_len > 128) {
        isc_throw(BadValue, "Cannot increase prefix: invalid prefix length: "
                  << prefix_len);
    }

102
103
104
    // Brief explanation what happens here:
    // http://www.youtube.com/watch?v=NFQCYpIHLNQ

105
106
107
108
    uint8_t n_bytes = (prefix_len - 1)/8;
    uint8_t n_bits = 8 - (prefix_len - n_bytes*8);
    uint8_t mask = 1 << n_bits;

109
110
111
112
113
114
115
    // Longer explanation: n_bytes specifies number of full bytes that are
    // in-prefix. They can also be used as an offset for the first byte that
    // is not in prefix. n_bits specifies number of bits on the last byte that
    // is (often partially) in prefix. For example for a /125 prefix, the values
    // are 15 and 3, respectively. Mask is a bitmask that has the least
    // significant bit from the prefix set.

116
117
118
119
120
    uint8_t packed[V6ADDRESS_LEN];

    // Copy the address. It must be V6, but we already checked that.
    std::memcpy(packed, &vec[0], V6ADDRESS_LEN);

121
    // Can we safely increase only the last byte in prefix without overflow?
122
123
124
125
126
127
128
129
    if (packed[n_bytes] + uint16_t(mask) < 256u) {
        packed[n_bytes] += mask;
        return (IOAddress::fromBytes(AF_INET6, packed));
    }

    // Overflow (done on uint8_t, but the sum is greater than 255)
    packed[n_bytes] += mask;

130
    // Deal with the overflow. Start increasing the least significant byte
131
132
133
134
135
136
137
138
139
140
141
    for (int i = n_bytes - 1; i >= 0; --i) {
        ++packed[i];
        // If we haven't overflowed (0xff->0x0) the next byte, then we are done
        if (packed[i] != 0) {
            break;
        }
    }

    return (IOAddress::fromBytes(AF_INET6, packed));
}

142

143
isc::asiolink::IOAddress
144
AllocEngine::IterativeAllocator::pickAddress(const SubnetPtr& subnet,
145
146
                                             const DuidPtr&,
                                             const IOAddress&) {
147

148
149
150
    // Is this prefix allocation?
    bool prefix = pool_type_ == Lease::TYPE_PD;

151
    // Let's get the last allocated address. It is usually set correctly,
152
    // but there are times when it won't be (like after removing a pool or
153
    // perhaps restarting the server).
Tomek Mrugalski's avatar
Tomek Mrugalski committed
154
    IOAddress last = subnet->getLastAllocated(pool_type_);
155

Tomek Mrugalski's avatar
Tomek Mrugalski committed
156
    const PoolCollection& pools = subnet->getPools(pool_type_);
157

158
    if (pools.empty()) {
159
160
161
162
        isc_throw(AllocFailed, "No pools defined in selected subnet");
    }

    // first we need to find a pool the last address belongs to.
163
    PoolCollection::const_iterator it;
164
165
166
167
168
169
170
171
172
173
174
175
176
    for (it = pools.begin(); it != pools.end(); ++it) {
        if ((*it)->inRange(last)) {
            break;
        }
    }

    // last one was bogus for one of several reasons:
    // - we just booted up and that's the first address we're allocating
    // - a subnet was removed or other reconfiguration just completed
    // - perhaps allocation algorithm was changed
    if (it == pools.end()) {
        // ok to access first element directly. We checked that pools is non-empty
        IOAddress next = pools[0]->getFirstAddress();
Tomek Mrugalski's avatar
Tomek Mrugalski committed
177
        subnet->setLastAllocated(pool_type_, next);
178
179
180
181
182
        return (next);
    }

    // Ok, we have a pool that the last address belonged to, let's use it.

183
184
    IOAddress next("::");
    if (!prefix) {
185
        next = IOAddress::increase(last); // basically addr++
186
187
188
189
    } else {
        Pool6Ptr pool6 = boost::dynamic_pointer_cast<Pool6>(*it);
        if (!pool6) {
            // Something is gravely wrong here
190
191
            isc_throw(Unexpected, "Wrong type of pool: " << (*it)->toText()
                      << " is not Pool6");
192
193
        }
        // Get the next prefix
Tomek Mrugalski's avatar
Tomek Mrugalski committed
194
        next = increasePrefix(last, pool6->getLength());
195
    }
196
    if ((*it)->inRange(next)) {
197
        // the next one is in the pool as well, so we haven't hit pool boundary yet
Tomek Mrugalski's avatar
Tomek Mrugalski committed
198
        subnet->setLastAllocated(pool_type_, next);
199
200
201
202
203
204
205
206
207
        return (next);
    }

    // We hit pool boundary, let's try to jump to the next pool and try again
    ++it;
    if (it == pools.end()) {
        // Really out of luck today. That was the last pool. Let's rewind
        // to the beginning.
        next = pools[0]->getFirstAddress();
Tomek Mrugalski's avatar
Tomek Mrugalski committed
208
        subnet->setLastAllocated(pool_type_, next);
209
210
211
        return (next);
    }

212
    // there is a next pool, let's try first address from it
213
    next = (*it)->getFirstAddress();
Tomek Mrugalski's avatar
Tomek Mrugalski committed
214
    subnet->setLastAllocated(pool_type_, next);
215
216
217
    return (next);
}

218
AllocEngine::HashedAllocator::HashedAllocator(Lease::Type lease_type)
219
    :Allocator(lease_type) {
220
221
222
223
224
    isc_throw(NotImplemented, "Hashed allocator is not implemented");
}


isc::asiolink::IOAddress
225
226
227
AllocEngine::HashedAllocator::pickAddress(const SubnetPtr&,
                                          const DuidPtr&,
                                          const IOAddress&) {
228
229
230
    isc_throw(NotImplemented, "Hashed allocator is not implemented");
}

231
AllocEngine::RandomAllocator::RandomAllocator(Lease::Type lease_type)
232
    :Allocator(lease_type) {
233
234
235
236
237
    isc_throw(NotImplemented, "Random allocator is not implemented");
}


isc::asiolink::IOAddress
238
239
240
AllocEngine::RandomAllocator::pickAddress(const SubnetPtr&,
                                          const DuidPtr&,
                                          const IOAddress&) {
241
242
243
    isc_throw(NotImplemented, "Random allocator is not implemented");
}

244

245
AllocEngine::AllocEngine(AllocType engine_type, uint64_t attempts,
246
                         bool ipv6)
247
248
    : attempts_(attempts), incomplete_v4_reclamations_(0),
      incomplete_v6_reclamations_(0) {
249

250
251
    // Choose the basic (normal address) lease type
    Lease::Type basic_type = ipv6 ? Lease::TYPE_NA : Lease::TYPE_V4;
252

253
    // Initalize normal address allocators
254
255
    switch (engine_type) {
    case ALLOC_ITERATIVE:
256
        allocators_[basic_type] = AllocatorPtr(new IterativeAllocator(basic_type));
257
258
        break;
    case ALLOC_HASHED:
259
        allocators_[basic_type] = AllocatorPtr(new HashedAllocator(basic_type));
260
261
        break;
    case ALLOC_RANDOM:
262
        allocators_[basic_type] = AllocatorPtr(new RandomAllocator(basic_type));
263
264
265
266
        break;
    default:
        isc_throw(BadValue, "Invalid/unsupported allocation algorithm");
    }
267

268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
    // If this is IPv6 allocation engine, initalize also temporary addrs
    // and prefixes
    if (ipv6) {
        switch (engine_type) {
        case ALLOC_ITERATIVE:
            allocators_[Lease::TYPE_TA] = AllocatorPtr(new IterativeAllocator(Lease::TYPE_TA));
            allocators_[Lease::TYPE_PD] = AllocatorPtr(new IterativeAllocator(Lease::TYPE_PD));
            break;
        case ALLOC_HASHED:
            allocators_[Lease::TYPE_TA] = AllocatorPtr(new HashedAllocator(Lease::TYPE_TA));
            allocators_[Lease::TYPE_PD] = AllocatorPtr(new HashedAllocator(Lease::TYPE_PD));
            break;
        case ALLOC_RANDOM:
            allocators_[Lease::TYPE_TA] = AllocatorPtr(new RandomAllocator(Lease::TYPE_TA));
            allocators_[Lease::TYPE_PD] = AllocatorPtr(new RandomAllocator(Lease::TYPE_PD));
            break;
        default:
            isc_throw(BadValue, "Invalid/unsupported allocation algorithm");
        }
    }

289
    // Register hook points
290
    hook_index_lease4_select_ = Hooks.hook_index_lease4_select_;
291
    hook_index_lease6_select_ = Hooks.hook_index_lease6_select_;
292
293
}

294
295
296
297
298
299
300
301
302
303
304
305
306
307
AllocEngine::AllocatorPtr AllocEngine::getAllocator(Lease::Type type) {
    std::map<Lease::Type, AllocatorPtr>::const_iterator alloc = allocators_.find(type);

    if (alloc == allocators_.end()) {
        isc_throw(BadValue, "No allocator initialized for pool type "
                  << Lease::typeToText(type));
    }
    return (alloc->second);
}

// ##########################################################################
// #    DHCPv6 lease allocation code starts here.
// ##########################################################################

308
309
310
311
AllocEngine::ClientContext6::ClientContext6()
    : subnet_(), duid_(), iaid_(0), type_(Lease::TYPE_NA), hwaddr_(),
      hints_(), fwd_dns_update_(false), rev_dns_update_(false), hostname_(""),
      callout_handle_(), fake_allocation_(false), old_leases_(), host_(),
312
      query_(), ia_rsp_() {
313
314
315
316
317
318
319
320
321
322
323
324
}

AllocEngine::ClientContext6::ClientContext6(const Subnet6Ptr& subnet, const DuidPtr& duid,
                                            const uint32_t iaid,
                                            const isc::asiolink::IOAddress& hint,
                                            const Lease::Type type, const bool fwd_dns,
                                            const bool rev_dns,
                                            const std::string& hostname,
                                            const bool fake_allocation):
    subnet_(subnet), duid_(duid), iaid_(iaid), type_(type), hwaddr_(),
    hints_(), fwd_dns_update_(fwd_dns), rev_dns_update_(rev_dns),
    hostname_(hostname), fake_allocation_(fake_allocation),
325
    old_leases_(), host_(), query_(), ia_rsp_() {
326
327
328
329
330
331
332
333
334
335
336

    static asiolink::IOAddress any("::");

    if (hint != any) {
        hints_.push_back(std::make_pair(hint, 128));
    }
    // callout_handle, host pointers initiated to NULL by their
    // respective constructors.
}


337
void AllocEngine::findReservation(ClientContext6& ctx) const {
338
339
    if (!ctx.subnet_ || !ctx.duid_) {
        return;
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
    }

    // Check which host reservation mode is supported in this subnet.
    Subnet::HRMode hr_mode = ctx.subnet_->getHostReservationMode();

    // Check if there's a host reservation for this client. Attempt to get
    // host info only if reservations are not disabled.
    if (hr_mode != Subnet::HR_DISABLED) {

        ctx.host_ = HostMgr::instance().get6(ctx.subnet_->getID(), ctx.duid_,
                                             ctx.hwaddr_);
        } else {
        // Let's explicitly set it to NULL if reservations are disabled.
        ctx.host_.reset();
    }
}
356

357
Lease6Collection
358
AllocEngine::allocateLeases6(ClientContext6& ctx) {
Tomek Mrugalski's avatar
Tomek Mrugalski committed
359

360
    try {
361
        if (!ctx.subnet_) {
Tomek Mrugalski's avatar
Tomek Mrugalski committed
362
363
            isc_throw(InvalidOperation, "Subnet is required for IPv6 lease allocation");
        } else
364
        if (!ctx.duid_) {
Tomek Mrugalski's avatar
Tomek Mrugalski committed
365
            isc_throw(InvalidOperation, "DUID is mandatory for IPv6 lease allocation");
366
        }
367

368
        // Check if there are existing leases for that subnet/duid/iaid
369
        // combination.
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
        Lease6Collection leases =
            LeaseMgrFactory::instance().getLeases6(ctx.type_, *ctx.duid_, ctx.iaid_,
                                                   ctx.subnet_->getID());

        // Now do the checks:
        // Case 1. if there are no leases, and there are reservations...
        //   1.1. are the reserved addresses are used by someone else?
        //       yes: we have a problem
        //       no: assign them => done
        // Case 2. if there are leases and there are no reservations...
        //   2.1 are the leases reserved for someone else?
        //       yes: release them, assign something else
        //       no: renew them => done
        // Case 3. if there are leases and there are reservations...
        //   3.1 are the leases matching reservations?
        //       yes: renew them => done
        //       no: release existing leases, assign new ones based on reservations
Tomek Mrugalski's avatar
Tomek Mrugalski committed
387
        // Case 4/catch-all. if there are no leases and no reservations...
388
389
390
391
392
        //       assign new leases
        //
        // We could implement those checks as nested ifs, but the performance
        // gain would be minimal and the code readibility loss would be substantial.
        // Hence independent checks.
393

394
        // Case 1: There are no leases and there's a reservation for this host.
Tomek Mrugalski's avatar
Tomek Mrugalski committed
395
        if (leases.empty() && ctx.host_) {
396

397
398
399
400
            LOG_DEBUG(alloc_engine_logger, ALLOC_ENGINE_DBG_TRACE,
                      ALLOC_ENGINE_V6_ALLOC_NO_LEASES_HR)
                .arg(ctx.query_->getLabel());

401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
            // Try to allocate leases that match reservations. Typically this will
            // succeed, except cases where the reserved addresses are used by
            // someone else.
            allocateReservedLeases6(ctx, leases);

            // If we got at least one lease, we're good to go.
            if (!leases.empty()) {
                return (leases);
            }

            // If not, we'll need to continue and will eventually fall into case 4:
            // getting a regular lease. That could happen when we're processing
            // request from client X, there's a reserved address A for X, but
            // A is currently used by client Y. We can't immediately reassign A
            // from X to Y, because Y keeps using it, so X would send Decline right
            // away. Need to wait till Y renews, then we can release A, so it
            // will become available for X.
418

419
420
421
422
423
        // Case 2: There are existing leases and there are no reservations.
        //
        // There is at least one lease for this client and there are no reservations.
        // We will return these leases for the client, but we may need to update
        // FQDN information.
424
        } else if (!leases.empty() && !ctx.host_) {
425

426
427
428
429
            LOG_DEBUG(alloc_engine_logger, ALLOC_ENGINE_DBG_TRACE,
                      ALLOC_ENGINE_V6_ALLOC_LEASES_NO_HR)
                .arg(ctx.query_->getLabel());

430
431
432
433
434
            // Check if the existing leases are reserved for someone else.
            // If they're not, we're ok to keep using them.
            removeNonmatchingReservedLeases6(ctx, leases);

            if (!leases.empty()) {
Tomek Mrugalski's avatar
Tomek Mrugalski committed
435
                // Return old leases so the server can see what has changed.
436
                return (updateLeaseData(ctx, leases));
437
438
            }

Tomek Mrugalski's avatar
Tomek Mrugalski committed
439
            // If leases are empty at this stage, it means that we used to have
440
441
442
443
            // leases for this client, but we checked and those leases are reserved
            // for someone else, so we lost them. We will need to continue and
            // will finally end up in case 4 (no leases, no reservations), so we'll
            // assign something new.
444

445
        // Case 3: There are leases and there are reservations.
446
        } else if (!leases.empty() && ctx.host_) {
447

448
449
450
451
            LOG_DEBUG(alloc_engine_logger, ALLOC_ENGINE_DBG_TRACE,
                      ALLOC_ENGINE_V6_ALLOC_LEASES_HR)
                .arg(ctx.query_->getLabel());

452
453
454
455
456
457
458
459
            // First, check if have leases matching reservations, and add new
            // leases if we don't have them.
            allocateReservedLeases6(ctx, leases);

            // leases now contain both existing and new leases that were created
            // from reservations.

            // Second, let's remove leases that are reserved for someone else.
Tomek Mrugalski's avatar
Tomek Mrugalski committed
460
461
462
463
464
465
            // This applies to any existing leases. This will not happen frequently,
            // but it may happen with the following chain of events:
            // 1. client A gets address X;
            // 2. reservation for client B for address X is made by a administrator;
            // 3. client A reboots
            // 4. client A requests the address (X) he got previously
466
467
468
469
470
471
472
473
474
475
476
            removeNonmatchingReservedLeases6(ctx, leases);

            // leases now contain existing and new leases, but we removed those
            // leases that are reserved for someone else (non-matching reserved).

            // There's one more check to do. Let's remove leases that are not
            // matching reservations, i.e. if client X has address A, but there's
            // a reservation for address B, we should release A and reassign B.
            // Caveat: do this only if we have at least one reserved address.
            removeNonreservedLeases6(ctx, leases);

Tomek Mrugalski's avatar
Tomek Mrugalski committed
477
            // All checks are done. Let's hope we have some leases left.
478
479
480
481

            // If we have any leases left, let's return them and we're done.
            if (!leases.empty()) {
                return (leases);
482
            }
483
484
485
486
487
488
489
490
491
492

            // If we don't have any leases at this stage, it means that we hit
            // one of the following cases:
            // - we have a reservation, but it's not for this IAID/ia-type and
            //   we had to return the address we were using
            // - we have a reservation for this iaid/ia-type, but the reserved
            //   address is currently used by someone else. We can't assign it
            //   yet.
            // - we had an address, but we just discovered that it's reserved for
            //   someone else, so we released it.
493
        }
494

Tomek Mrugalski's avatar
Tomek Mrugalski committed
495
        // Case 4/catch-all: One of the following is true:
496
497
498
499
500
        // - we don't have leases and there are no reservations
        // - we used to have leases, but we lost them, because they are now
        //   reserved for someone else
        // - we have a reservation, but it is not usable yet, because the address
        //   is still used by someone else
501
        //
502
        // In any case, we need to go through normal lease assignment process
503
        // for now. This is also a catch-all or last resort approach, when we
Tomek Mrugalski's avatar
Tomek Mrugalski committed
504
        // couldn't find any reservations (or couldn't use them).
505

506
507
508
509
        LOG_DEBUG(alloc_engine_logger, ALLOC_ENGINE_DBG_TRACE,
                  ALLOC_ENGINE_V6_ALLOC_UNRESERVED)
            .arg(ctx.query_->getLabel());

510
        leases = allocateUnreservedLeases6(ctx);
511

Tomek Mrugalski's avatar
Tomek Mrugalski committed
512
513
514
        if (!leases.empty()) {
            return (leases);
        }
515

516
517
518
519

    } catch (const isc::Exception& e) {

        // Some other error, return an empty lease.
520
521
522
        LOG_ERROR(alloc_engine_logger, ALLOC_ENGINE_V6_ALLOC_ERROR)
            .arg(ctx.query_->getLabel())
            .arg(e.what());
523
    }
524

525
    return (Lease6Collection());
526
527
}

528
529
530
531
532
533
534
535
536
Lease6Collection
AllocEngine::allocateUnreservedLeases6(ClientContext6& ctx) {

    AllocatorPtr allocator = getAllocator(ctx.type_);

    if (!allocator) {
        isc_throw(InvalidOperation, "No allocator specified for "
                  << Lease6::typeToText(ctx.type_));
    }
537

538
539
540
    // Check which host reservation mode is supported in this subnet.
    Subnet::HRMode hr_mode = ctx.subnet_->getHostReservationMode();

541
542
    Lease6Collection leases;

543
    IOAddress hint = IOAddress::IPV6_ZERO_ADDRESS();
544
545
    if (!ctx.hints_.empty()) {
        /// @todo: We support only one hint for now
546
        hint = ctx.hints_[0].first;
547
548
549
550
551
552
553
554
555
556
557
558
    }

    // check if the hint is in pool and is available
    // This is equivalent of subnet->inPool(hint), but returns the pool
    Pool6Ptr pool = boost::dynamic_pointer_cast<
        Pool6>(ctx.subnet_->getPool(ctx.type_, hint, false));

    if (pool) {
        /// @todo: We support only one hint for now
        Lease6Ptr lease = LeaseMgrFactory::instance().getLease6(ctx.type_, hint);
        if (!lease) {

559
560
561
562
            // In-pool reservations: Check if this address is reserved for someone
            // else. There is no need to check for whom it is reserved, because if
            // it has been reserved for us we would have already allocated a lease.

563
564
565
566
567
568
            ConstHostPtr host;
            if (hr_mode != Subnet::HR_DISABLED) {
                host = HostMgr::instance().get6(ctx.subnet_->getID(), hint);
            }

            if (!host) {
569
570
                // If the in-pool reservations are disabled, or there is no
                // reservation for a given hint, we're good to go.
571
572
573

                // The hint is valid and not currently used, let's create a
                // lease for it
574
                lease = createLease6(ctx, hint, pool->getLength());
575

576
577
                // It can happen that the lease allocation failed (we could
                // have lost the race condition. That means that the hint is
Tomek Mrugalski's avatar
Tomek Mrugalski committed
578
                // no longer usable and we need to continue the regular
579
                // allocation path.
580
                if (lease) {
581

582
583
584
585
                    /// @todo: We support only one lease per ia for now
                    Lease6Collection collection;
                    collection.push_back(lease);
                    return (collection);
586
                }
587
588
589
590
591
            } else {
                LOG_DEBUG(alloc_engine_logger, ALLOC_ENGINE_DBG_TRACE,
                          ALLOC_ENGINE_V6_HINT_RESERVED)
                    .arg(ctx.query_->getLabel())
                    .arg(hint.toText());
592
            }
593

594
        } else {
595
596

            // If the lease is expired, we may likely reuse it, but...
597
598
            if (lease->expired()) {

599
600
601
602
603
                ConstHostPtr host;
                if (hr_mode != Subnet::HR_DISABLED) {
                    host = HostMgr::instance().get6(ctx.subnet_->getID(), hint);
                }

604
                // Let's check if there is a reservation for this address.
605
                if (!host) {
606

607
608
609
                    // Copy an existing, expired lease so as it can be returned
                    // to the caller.
                    Lease6Ptr old_lease(new Lease6(*lease));
610
                    ctx.old_leases_.push_back(old_lease);
611

612
                    /// We found a lease and it is expired, so we can reuse it
613
                    lease = reuseExpiredLease(lease, ctx, pool->getLength());
614
615

                    /// @todo: We support only one lease per ia for now
616
617
                    leases.push_back(lease);
                    return (leases);
618
619
620
621
622
623

                } else {
                    LOG_DEBUG(alloc_engine_logger, ALLOC_ENGINE_DBG_TRACE,
                              ALLOC_ENGINE_V6_EXPIRED_HINT_RESERVED)
                        .arg(ctx.query_->getLabel())
                        .arg(hint.toText());
624
625
                }
            }
626
        }
627
    }
628

Tomek Mrugalski's avatar
Tomek Mrugalski committed
629
630
631
    // The hint was useless (it was not provided at all, was used by someone else,
    // was out of pool or reserved for someone else). Search the pool until first
    // of the following occurs:
632
633
634
    // - we find a free address
    // - we find an address for which the lease has expired
    // - we exhaust number of tries
635
636
    uint64_t max_attempts = (attempts_ > 0 ? attempts_  :
                             ctx.subnet_->getPoolCapacity(ctx.type_));
637
    for (uint64_t i = 0; i < max_attempts; ++i)
638
    {
639
640
        IOAddress candidate = allocator->pickAddress(ctx.subnet_, ctx.duid_, hint);

641
642
643
        /// In-pool reservations: Check if this address is reserved for someone
        /// else. There is no need to check for whom it is reserved, because if
        /// it has been reserved for us we would have already allocated a lease.
644
        if (hr_mode == Subnet::HR_ALL &&
645
646
647
648
649
            HostMgr::instance().get6(ctx.subnet_->getID(), candidate)) {

            // Don't allocate.
            continue;
        }
650

651
652
653
654
655
656
        // The first step is to find out prefix length. It is 128 for
        // non-PD leases.
        uint8_t prefix_len = 128;
        if (ctx.type_ == Lease::TYPE_PD) {
            Pool6Ptr pool = boost::dynamic_pointer_cast<Pool6>(
                ctx.subnet_->getPool(ctx.type_, candidate, false));
657
            /// @todo: verify that the pool is non-null
658
659
            prefix_len = pool->getLength();
        }
660

661
662
663
        Lease6Ptr existing = LeaseMgrFactory::instance().getLease6(ctx.type_,
                                                                   candidate);
        if (!existing) {
664

665
666
            // there's no existing lease for selected candidate, so it is
            // free. Let's allocate it.
667

668
669
670
671
672
            Lease6Ptr lease = createLease6(ctx, candidate, prefix_len);
            if (lease) {
                // We are allocating a new lease (not renewing). So, the
                // old lease should be NULL.
                ctx.old_leases_.clear();
673

Tomek Mrugalski's avatar
Tomek Mrugalski committed
674
675
                leases.push_back(lease);
                return (leases);
676
            }
677

678
679
680
681
682
683
684
685
686
687
688
689
690
            // Although the address was free just microseconds ago, it may have
            // been taken just now. If the lease insertion fails, we continue
            // allocation attempts.
        } else {
            if (existing->expired()) {
                // Copy an existing, expired lease so as it can be returned
                // to the caller.
                Lease6Ptr old_lease(new Lease6(*existing));
                ctx.old_leases_.push_back(old_lease);

                existing = reuseExpiredLease(existing,
                                             ctx,
                                             prefix_len);
Tomek Mrugalski's avatar
Tomek Mrugalski committed
691
692
693

                leases.push_back(existing);
                return (leases);
694
            }
695
        }
696
    }
697

698
699
700
701
702
703
704
    // Unable to allocate an address, return an empty lease.
    LOG_WARN(alloc_engine_logger, ALLOC_ENGINE_V6_ALLOC_FAIL)
        .arg(ctx.query_->getLabel())
        .arg(max_attempts);



705
706
707
    // We failed to allocate anything. Let's return empty collection.
    return (Lease6Collection());
}
708

709
710
void
AllocEngine::allocateReservedLeases6(ClientContext6& ctx, Lease6Collection& existing_leases) {
711

712
    // If there are no reservations or the reservation is v4, there's nothing to do.
713
    if (!ctx.host_ || !ctx.host_->hasIPv6Reservation()) {
714
715
716
        LOG_DEBUG(alloc_engine_logger, ALLOC_ENGINE_DBG_TRACE,
                  ALLOC_ENGINE_V6_ALLOC_NO_V6_HR)
            .arg(ctx.query_->getLabel());
717
        return;
718
    }
719

720
721
722
723
724
725
726
727
728
729
    // Let's convert this from Lease::Type to IPv6Reserv::Type
    IPv6Resrv::Type type = ctx.type_ == Lease::TYPE_NA ? IPv6Resrv::TYPE_NA : IPv6Resrv::TYPE_PD;

    // Get the IPv6 reservations of specified type.
    const IPv6ResrvRange& reservs = ctx.host_->getIPv6Reservations(type);
    for (IPv6ResrvIterator resv = reservs.first; resv != reservs.second; ++resv) {
        // We do have a reservation for addr.
        IOAddress addr = resv->second.getPrefix();
        uint8_t prefix_len = resv->second.getPrefixLen();

730
        // Check if already have this lease on the existing_leases list.
731
        for (Lease6Collection::iterator l = existing_leases.begin();
732
733
734
735
             l != existing_leases.end(); ++l) {

            // Ok, we already have a lease for this reservation and it's usable
            if (((*l)->addr_ == addr) && (*l)->valid_lft_ != 0) {
736
737
738
739
740
                LOG_DEBUG(alloc_engine_logger, ALLOC_ENGINE_DBG_TRACE,
                          ALLOC_ENGINE_V6_ALLOC_HR_LEASE_EXISTS)
                    .arg(ctx.query_->getLabel())
                    .arg((*l)->typeToText((*l)->type_))
                    .arg((*l)->addr_.toText());
741
742
743
744
745
746
747

                // If this is a real allocation, we may need to extend the lease
                // lifetime.
                if (!ctx.fake_allocation_ && conditionalExtendLifetime(**l)) {
                    LeaseMgrFactory::instance().updateLease6(*l);
                }

748
749
750
751
                return;
            }
        }

752
753
        // If there's a lease for this address, let's not create it.
        // It doesn't matter whether it is for this client or for someone else.
754
755
756
        if (!LeaseMgrFactory::instance().getLease6(ctx.type_, addr)) {
            // Ok, let's create a new lease...
            Lease6Ptr lease = createLease6(ctx, addr, prefix_len);
757

758
759
            // ... and add it to the existing leases list.
            existing_leases.push_back(lease);
760

761
            if (ctx.type_ == Lease::TYPE_NA) {
762
                LOG_INFO(alloc_engine_logger, ALLOC_ENGINE_V6_HR_ADDR_GRANTED)
763
764
                    .arg(addr.toText())
                    .arg(ctx.query_->getLabel());
765
            } else {
766
                LOG_INFO(alloc_engine_logger, ALLOC_ENGINE_V6_HR_PREFIX_GRANTED)
767
768
769
                    .arg(addr.toText())
                    .arg(static_cast<int>(prefix_len))
                    .arg(ctx.query_->getLabel());
770
            }
771

772
773
774
775
776
777
778
779
780
781
            // We found a lease for this client and this IA. Let's return.
            // Returning after the first lease was assigned is useful if we
            // have multiple reservations for the same client. If the client
            // sends 2 IAs, the first time we call allocateReservedLeases6 will
            // use the first reservation and return. The second time, we'll
            // go over the first reservation, but will discover that there's
            // a lease corresponding to it and will skip it and then pick
            // the second reservation and turn it into the lease. This approach
            // would work for any number of reservations.
            return;
782
        }
783
    }
784
785
786
787
788
}

void
AllocEngine::removeNonmatchingReservedLeases6(ClientContext6& ctx,
                                              Lease6Collection& existing_leases) {
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
    // If there are no leases (so nothing to remove) or
    // host reservation is disabled (so there are no reserved leases),
    // just return.
    if (existing_leases.empty() || !ctx.subnet_ ||
        (ctx.subnet_->getHostReservationMode() == Subnet::HR_DISABLED) ) {
        return;
    }

    // We need a copy, so we won't be iterating over a container and
    // removing from it at the same time. It's only a copy of pointers,
    // so the operation shouldn't be that expensive.
    Lease6Collection copy = existing_leases;

    for (Lease6Collection::const_iterator candidate = copy.begin();
         candidate != copy.end(); ++candidate) {

        ConstHostPtr host = HostMgr::instance().get6(ctx.subnet_->getID(),
                                                     (*candidate)->addr_);

808
        if (!host || (host == ctx.host_)) {
809
810
811
812
813
814
815
            // Not reserved or reserved for us. That's ok, let's check
            // the next lease.
            continue;
        }

        // Ok, we have a problem. This host has a lease that is reserved
        // for someone else. We need to recover from this.
816
        if (ctx.type_ == Lease::TYPE_NA) {
817
            LOG_INFO(alloc_engine_logger, ALLOC_ENGINE_V6_REVOKED_ADDR_LEASE)
818
819
820
                .arg((*candidate)->addr_.toText()).arg(ctx.duid_->toText())
                .arg(host->getIdentifierAsText());
        } else {
821
            LOG_INFO(alloc_engine_logger, ALLOC_ENGINE_V6_REVOKED_PREFIX_LEASE)
822
823
824
825
826
                .arg((*candidate)->addr_.toText())
                .arg(static_cast<int>((*candidate)->prefixlen_))
                .arg(ctx.duid_->toText())
                .arg(host->getIdentifierAsText());
        }
827
828
829
830

        // Remove this lease from LeaseMgr
        LeaseMgrFactory::instance().deleteLease((*candidate)->addr_);

831
832
833
        // Update DNS if needed.
        queueNCR(CHG_REMOVE, *candidate);

834
835
836
        // Need to decrease statistic for assigned addresses.
        StatsMgr::instance().addValue(
            StatsMgr::generateName("subnet", ctx.subnet_->getID(),
837
838
                                   ctx.type_ == Lease::TYPE_NA ? "assigned-nas" :
                                                                 "assigned-pds"),
839
840
            static_cast<int64_t>(-1));

841
842
843
844
        // In principle, we could trigger a hook here, but we will do this
        // only if we get serious complaints from actual users. We want the
        // conflict resolution procedure to really work and user libraries
        // should not interfere with it.
845
846
847

        // Add this to the list of removed leases.
        ctx.old_leases_.push_back(*candidate);
848
849
850

        // Let's remove this candidate from existing leases
        removeLeases(existing_leases, (*candidate)->addr_);
851
852
853
    }
}

854
855
856
bool
AllocEngine::removeLeases(Lease6Collection& container, const asiolink::IOAddress& addr) {

Tomek Mrugalski's avatar
Tomek Mrugalski committed
857
    bool removed = false;
858
859
860
    for (Lease6Collection::iterator lease = container.begin();
         lease != container.end(); ++lease) {
        if ((*lease)->addr_ == addr) {
Tomek Mrugalski's avatar
Tomek Mrugalski committed
861
862
            lease->reset();
            removed = true;
863
864
865
        }
    }

Tomek Mrugalski's avatar
Tomek Mrugalski committed
866
867
868
869
870
    // Remove all elements that have NULL value
    container.erase(std::remove(container.begin(), container.end(), Lease6Ptr()),
                    container.end());

    return (removed);
871
872
}

873
874
875
void
AllocEngine::removeNonreservedLeases6(ClientContext6& ctx,
                                      Lease6Collection& existing_leases) {
876
877
878
    // This method removes leases that are not reserved for this host.
    // It will keep at least one lease, though.
    if (existing_leases.empty() || !ctx.host_ || !ctx.host_->hasIPv6Reservation()) {
879
        return;
880
    }
881
882
883
884

    // This is the total number of leases. We should not remove the last one.
    int total = existing_leases.size();

Tomek Mrugalski's avatar
Tomek Mrugalski committed
885
886
    // This is officially not scary code anymore. iterates and marks specified
    // leases for deletion, by setting appropriate pointers to NULL.
887
    for (Lease6Collection::iterator lease = existing_leases.begin();
Tomek Mrugalski's avatar
Tomek Mrugalski committed
888
         lease != existing_leases.end(); ++lease) {
889
890
        IPv6Resrv resv(ctx.type_ == Lease::TYPE_NA ? IPv6Resrv::TYPE_NA : IPv6Resrv::TYPE_PD,
                       (*lease)->addr_, (*lease)->prefixlen_);
Tomek Mrugalski's avatar
Tomek Mrugalski committed
891
        if (!ctx.host_->hasReservation(resv)) {
892
893
894
895
896
            // We have reservations, but not for this lease. Release it.

            // Remove this lease from LeaseMgr
            LeaseMgrFactory::instance().deleteLease((*lease)->addr_);

897
898
899
            // Update DNS if required.
            queueNCR(CHG_REMOVE, *lease);

900
901
902
            // Need to decrease statistic for assigned addresses.
            StatsMgr::instance().addValue(
                StatsMgr::generateName("subnet", ctx.subnet_->getID(),
903
904
                                       ctx.type_ == Lease::TYPE_NA ? "assigned-nas" :
                                                                     "assigned-pds"),
905
906
                static_cast<int64_t>(-1));

907
908
909
910
911
            /// @todo: Probably trigger a hook here

            // Add this to the list of removed leases.
            ctx.old_leases_.push_back(*lease);

Tomek Mrugalski's avatar
Tomek Mrugalski committed
912
913
914
915
            // Set this pointer to NULL. The pointer is still valid. We're just
            // setting the Lease6Ptr to NULL value. We'll remove all NULL
            // pointers once the loop is finished.
            lease->reset();
916
917

            if (--total == 1) {
Tomek Mrugalski's avatar
Tomek Mrugalski committed
918
919
                // If there's only one lease left, break the loop.
                break;
920
921
922
923
            }
        }

    }
Tomek Mrugalski's avatar
Tomek Mrugalski committed
924
925
926
927
928

    // Remove all elements that we previously marked for deletion (those that
    // have NULL value).
    existing_leases.erase(std::remove(existing_leases.begin(),
        existing_leases.end(), Lease6Ptr()), existing_leases.end());
929
930
}

931
932
933
Lease6Ptr
AllocEngine::reuseExpiredLease(Lease6Ptr& expired, ClientContext6& ctx,
                               uint8_t prefix_len) {
934
935
936
937
938

    if (!expired->expired()) {
        isc_throw(BadValue, "Attempt to recycle lease that is still valid");
    }

939
940
941
942
    if (expired->type_ != Lease::TYPE_PD) {
        prefix_len = 128; // non-PD lease types must be always /128
    }

943
944
945
946
947
    if (!ctx.fake_allocation_) {
        // The expired lease needs to be reclaimed before it can be reused.
        // This includes declined leases for which probation period has
        // elapsed.
        reclaimExpiredLease(expired, ctx.callout_handle_);
948
949
    }

950
    // address, lease type and prefixlen (0) stay the same
951
952
953
954
955
956
    expired->iaid_ = ctx.iaid_;
    expired->duid_ = ctx.duid_;
    expired->preferred_lft_ = ctx.subnet_->getPreferred();
    expired->valid_lft_ = ctx.subnet_->getValid();
    expired->t1_ = ctx.subnet_->getT1();
    expired->t2_ = ctx.subnet_->getT2();
957
    expired->cltt_ = time(NULL);
958
959
960
961
    expired->subnet_id_ = ctx.subnet_->getID();
    expired->hostname_ = ctx.hostname_;
    expired->fqdn_fwd_ = ctx.fwd_dns_update_;
    expired->fqdn_rev_ = ctx.rev_dns_update_;
962
    expired->prefixlen_ = prefix_len;
963
    expired->state_ = Lease::STATE_DEFAULT;
964

965
966
967
968
    LOG_DEBUG(alloc_engine_logger, ALLOC_ENGINE_DBG_TRACE_DETAIL_DATA,
              ALLOC_ENGINE_V6_REUSE_EXPIRED_LEASE_DATA)
        .arg(ctx.query_->getLabel())
        .arg(expired->toText());
969

Tomek Mrugalski's avatar
Tomek Mrugalski committed
970
    // Let's execute all callouts registered for lease6_select
971
    if (ctx.callout_handle_ &&
972
973
974
        HooksManager::getHooksManager().calloutsPresent(hook_index_lease6_select_)) {

        // Delete all previous arguments
975
        ctx.callout_handle_->deleteAllArguments();
976
977
978

        // Pass necessary arguments
        // Subnet from which we do the allocation
979
        ctx.callout_handle_->setArgument("subnet6", ctx.subnet_);
980
981

        // Is this solicit (fake = true) or request (fake = false)
982
        ctx.callout_handle_->setArgument("fake_allocation", ctx.fake_allocation_);
Tomek Mrugalski's avatar
Tomek Mrugalski committed
983
984

        // The lease that will be assigned to a client
985
        ctx.callout_handle_->setArgument("lease6", expired);
986

Tomek Mrugalski's avatar
Tomek Mrugalski committed
987
        // Call the callouts
988
        HooksManager::callCallouts(hook_index_lease6_select_, *ctx.callout_handle_);
989
990
991

        // Callouts decided to skip the action. This means that the lease is not
        // assigned, so the client will get NoAddrAvail as a result. The lease
992
        // won't be inserted into the database.
993
        if (ctx.callout_handle_->getStatus() == CalloutHandle::NEXT_STEP_SKIP) {
994
            LOG_DEBUG(dhcpsrv_logger, DHCPSRV_DBG_HOOKS, DHCPSRV_HOOK_LEASE6_SELECT_SKIP);
995
996
997
            return (Lease6Ptr());
        }

998
999
        /// @todo: Add support for DROP status

1000
        // Let's use whatever callout returned. Hopefully it is the same lease
Shawn Routhier's avatar
Shawn Routhier committed
1001
        // we handed to it.
1002
        ctx.callout_handle_->getArgument("lease6", expired);
1003
1004
    }

1005
    if (!ctx.fake_allocation_) {
1006
1007
        // for REQUEST we do update the lease
        LeaseMgrFactory::instance().updateLease6(expired);
Tomek Mrugalski's avatar
Tomek Mrugalski committed
1008
    }
1009
1010
1011
1012
1013
1014
1015
1016
1017

    // We do nothing for SOLICIT. We'll just update database when
    // the client gets back to us with REQUEST message.

    // it's not really expired at this stage anymore - let's return it as
    // an updated lease
    return (expired);
}

1018
1019
1020
Lease6Ptr AllocEngine::createLease6(ClientContext6& ctx,
                                    const IOAddress& addr,
                                    uint8_t prefix_len) {
1021

1022
1023
    if (ctx.type_ != Lease::TYPE_PD) {
        prefix_len = 128; // non-PD lease types must be always /128
1024
1025
    }

1026
1027
1028
1029
    Lease6Ptr lease(new Lease6(ctx.type_, addr, ctx.duid_, ctx.iaid_,
                               ctx.subnet_->getPreferred(), ctx.subnet_->getValid(),
                               ctx.subnet_->getT1(), ctx.subnet_->getT2(),
                               ctx.subnet_->getID(), ctx.hwaddr_, prefix_len));
1030

1031
1032
1033
    lease->fqdn_fwd_ = ctx.fwd_dns_update_;
    lease->fqdn_rev_ = ctx.rev_dns_update_;
    lease->hostname_ = ctx.hostname_;
1034

1035
1036
1037
    // Let's execute all callouts registered for lease6_select
    if (ctx.callout_handle_ &&
        HooksManager::getHooksManager().calloutsPresent(hook_index_lease6_select_)) {
1038
1039

        // Delete all previous arguments
1040
        ctx.callout_handle_->deleteAllArguments();
1041
1042

        // Pass necessary arguments
1043

1044
1045
        // Subnet from which we do the allocation
        ctx.callout_handle_->setArgument("subnet6", ctx.subnet_);
1046
1047

        // Is this solicit (fake = true) or request (fake = false)
1048
1049
        ctx.callout_handle_->setArgument("fake_allocation", ctx.fake_allocation_);
        ctx.callout_handle_->setArgument("lease6", lease);
1050

1051
1052
        // This is the first callout, so no need to clear any arguments
        HooksManager::callCallouts(hook_index_lease6_select_, *ctx.callout_handle_);
1053
1054
1055

        // Callouts decided to skip the action. This means that the lease is not
        // assigned, so the client will get NoAddrAvail as a result. The lease
1056
        // won't be inserted into the database.
1057
        if (ctx.callout_handle_->getStatus() == CalloutHandle::NEXT_STEP_SKIP) {
1058
1059
            LOG_DEBUG(dhcpsrv_logger, DHCPSRV_DBG_HOOKS, DHCPSRV_HOOK_LEASE6_SELECT_SKIP);
            return (Lease6Ptr());
1060
1061
1062
        }

        // Let's use whatever callout returned. Hopefully it is the same lease
Shawn Routhier's avatar
Shawn Routhier committed
1063
        // we handed to it.
1064
        ctx.callout_handle_->getArgument("lease6", lease);
1065
1066
    }

1067
    if (!ctx.fake_allocation_) {
1068
1069
        // That is a real (REQUEST) allocation
        bool status = LeaseMgrFactory::instance().addLease(lease);
1070

1071
        if (status) {
Shawn Routhier's avatar
Shawn Routhier committed
1072
1073
1074
1075
1076
            // The lease insertion succeeded - if the lease is in the
            // current subnet lets bump up the statistic.
            if (ctx.subnet_->inPool(ctx.type_, addr)) {
                StatsMgr::instance().addValue(
                    StatsMgr::generateName("subnet", ctx.subnet_->getID(),
1077
1078
                                           ctx.type_ == Lease::TYPE_NA ? "assigned-nas" :
                                                                         "assigned-pds"),
Shawn Routhier's avatar
Shawn Routhier committed
1079