// Copyright 2017 The Fuchsia Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include <ddk/phys-iter.h>
#include <sys/param.h>
#include <zircon/assert.h>

#include <string.h>

// Returns the buffer offset of the start of the current segment being iterated over.
static size_t segment_offset(phys_iter_t* iter) {
    // The physical pages list begins with the page containing buf->vmo_offset,
    // while the stored segment_offset is relative to the buffer vmo offset.
    return (iter->buf.vmo_offset & (PAGE_SIZE - 1)) + iter->segment_offset;
}

// Initializes the iterator for the next segment to iterate over.
// Returns whether there was a next segment.
static bool init_next_sg_entry(phys_iter_t* iter) {
    // Finished iterating through the scatter gather list.
    if (iter->buf.sg_list && iter->next_sg_entry_idx >= iter->buf.sg_count) {
        return false;
    }
    // No scatter gather list was provided and we have finished iterating
    // over the requested length.
    if (!iter->buf.sg_list && iter->total_iterated == iter->buf.length) {
        return false;
    }
    if (iter->buf.sg_list) {
        phys_iter_sg_entry_t* next = &iter->buf.sg_list[iter->next_sg_entry_idx];
        iter->segment_length = next->length;
        iter->segment_offset = next->offset;
        iter->next_sg_entry_idx++;
    } else {
        iter->segment_length = iter->buf.length;
        iter->segment_offset = 0;
    }

    iter->offset = 0;
    // iter->page is index of page containing the next segment start offset.
    // and iter->last_page is index of page containing the segment offset + segment->length
    iter->page = iter->buf.phys_count == 1 ? 0 : segment_offset(iter) / PAGE_SIZE;
    if (iter->segment_length > 0) {
        iter->last_page = (iter->segment_length + segment_offset(iter) - 1) / PAGE_SIZE;
        iter->last_page = MIN(iter->last_page, iter->buf.phys_count - 1);
    } else {
        iter->last_page = 0;
    }
    return true;
}

void phys_iter_init(phys_iter_t* iter, phys_iter_buffer_t* buf, size_t max_length) {
    memset(iter, 0, sizeof(phys_iter_t));
    memcpy(&iter->buf, buf, sizeof(phys_iter_buffer_t));
    ZX_DEBUG_ASSERT(max_length % PAGE_SIZE == 0);
    if (max_length == 0) {
        max_length = UINT64_MAX;
    }
    iter->max_length = max_length;
    init_next_sg_entry(iter);
}

static inline void phys_iter_increment(phys_iter_t* iter, size_t len) {
    iter->total_iterated += len;
    iter->offset += len;
}

size_t phys_iter_next(phys_iter_t* iter, zx_paddr_t* out_paddr) {
    // Check if we've finished iterating over the current segment.
    // We shouldn't have any zero length segments, but use a while loop just in case.
    while (iter->offset >= iter->segment_length) {
        bool has_next = init_next_sg_entry(iter);
        if (!has_next) {
            return 0;
        }
    }

    phys_iter_buffer_t buf = iter->buf;
    zx_off_t offset = iter->offset;
    size_t max_length = iter->max_length;
    size_t length = iter->segment_length;

    size_t remaining = length - offset;
    zx_paddr_t* phys_addrs = buf.phys;
    size_t align_adjust = segment_offset(iter) & (PAGE_SIZE - 1);
    zx_paddr_t phys = phys_addrs[iter->page];
    size_t return_length = 0;

    if (buf.phys_count == 1) {
        // simple contiguous case
        *out_paddr = phys_addrs[0] + offset + segment_offset(iter);
        return_length = remaining;
        if (return_length > max_length) {
            // end on a page boundary
            return_length = max_length - align_adjust;
        }
        phys_iter_increment(iter, return_length);
        return return_length;
    }

    if (offset == 0 && align_adjust > 0) {
        // if the segment offset is unaligned we need to adjust out_paddr, accumulate partial
        // page length in return_length and skip to next page.
        // we will make sure the range ends on a page boundary so we don't need to worry about
        // alignment for subsequent iterations.
        *out_paddr = phys + align_adjust;
        return_length = MIN(PAGE_SIZE - align_adjust, remaining);
        remaining -= return_length;
        iter->page++;

        if (iter->page > iter->last_page || phys + PAGE_SIZE != phys_addrs[iter->page]) {
            phys_iter_increment(iter, return_length);
            return return_length;
        }
        phys = phys_addrs[iter->page];
    } else {
        *out_paddr = phys;
    }

    // below is more complicated case where we need to watch for discontinuities
    // in the physical address space.

    // loop through physical addresses looking for discontinuities
    while (remaining > 0 && iter->page <= iter->last_page) {
        const size_t increment = MIN(PAGE_SIZE, remaining);
        if (return_length + increment > max_length) {
            break;
        }
        return_length += increment;
        remaining -= increment;
        iter->page++;

        if (iter->page > iter->last_page) {
            break;
        }

        zx_paddr_t next = phys_addrs[iter->page];
        if (phys + PAGE_SIZE != next) {
            break;
        }
        phys = next;
    }

    if (return_length > max_length) {
        return_length = max_length;
    }
    phys_iter_increment(iter, return_length);
    return return_length;
}