/////////////////////////////////////////////////////////////////////////////// // // =========== LEGAL NOTICE =========== // // These coded instructions, | Unauthorised use, copying, modification, // statements, and computer | distribution, sale or disclosure to third // software contain unpublished | parties of this code, in whole or in part, // proprietary information of | is strictly prohibited without the prior // Proximity Pty Ltd. | written permission of the copyright owners. // // Copyright (c) 1996 Proximity Pty Ltd. // /////////////////////////////////////////////////////////////////////////////// // $Id: KrBuf.C,v 1.1 2000/03/10 16:15:10 ben Exp $ // bjm 20/12/95 #include #include #include #include #include #include #include #include #include #ifndef IOV_MAX #define IOV_MAX 16 // this seems to be so on most systems #endif // // Defining DEBUG on this file enables the following : // // * Defines the functions KrBuf::verify() and KrBuf::dump(), // #define DEBUG 1 // compiles in debugging messages //#define KRBUF_DEBUG 1 // uses read() instead of readv() to avoid purify UMR bug //#define PURIFY_BUG 1 //----------------------------------------------------------------------------- // KrBuf default constructor // KrBuf::KrBuf() { _mHead = _mTail = NULL; _size = 0; #ifdef KRBUF_DEBUG cerr << "KrBuf::KrBuf() " << this << " _size -> 0" << endl; #endif } //----------------------------------------------------------------------------- // KrBuf destructor // KrBuf::~KrBuf() { if (_mHead) mFreem(_mHead); #ifdef KRBUF_DEBUG cerr << "KrBuf::~KrBuf() " << this << " _size -> 0" << endl; #endif } //----------------------------------------------------------------------------- // struct KrBuf::MBuf* KrBuf::mAlloc(); // // This returns a single mbuf from the KrPool. // struct KrBuf::MBuf* KrBuf::mAlloc() { MBuf* m = (MBuf*) KrPool::alloc(); m->_next = NULL; m->_data = m->_dat; m->_len = 0; return m; } //----------------------------------------------------------------------------- //----------------------------------------------------------------------------- // void* KrBuf::get(void* data, int len, int pos, bool alwaysCopy); // // Return a pointer to a contiguous block of data of length (len), as obtained // from the KrBuf starting from position (pos). If the data is NOT // contiguously visible in an mbuf without reshuffling, the data is copied // into the user-supplied buffer (data), and a pointer to that buffer is // returned. If the data IS contiguously visible, the behaviour depends on the // alwaysCopy flag. If true (the default), the data is copied as above. // If false, a pointer to the data in the mbuf is returned instead. // void* KrBuf::get(void* data, int len, int pos, bool alwaysCopy) { assert (pos + len <= _size); if (len == 0) return NULL; register MBuf* m = _mHead; while (pos >= m->_len) { pos -= m->_len; m = m->_next; } int chunk = min(m->_len - pos, len); if (!alwaysCopy && chunk == len) return m->_data + pos; void* r = data; ::memcpy(data, m->_data + pos, chunk); while (len -= chunk) { data = (char*)data + chunk; m = m->_next; chunk = min(m->_len, len); ::memcpy(data, m->_data, chunk); } return r; } //----------------------------------------------------------------------------- // void* KrBuf::get(int len, int pos); // // Return a pointer to a contiguous window of the KrBuf, of (len) bytes, // starting from (pos). This may require shuffling data around to make sure // the whole window is within a single mbuf. A consequence of this is that // (len) must be less than or equal to (KRBUF_MLEN). // void* KrBuf::get(int len, int pos) { assert (len > 0); assert (pos >= 0); assert (pos + len <= _size); register MBuf* m = _mHead; while (pos >= m->_len) { pos -= m->_len; m = m->_next; } // Can we see all of the data now? If so, return immediately. if (m->_len - pos >= len) return m->_data + pos; // Defer this check to here, as the above check does not depend on it, // and it's going to succeed far more often than this check fails. assert (len <= KRBUF_MLEN); // We're gonna have to copy some data around to make the contiguous // data area we need. Can we fit it without moving anything in the // current mbuf? if ((m->_data - m->_dat) + pos + len > KRBUF_MLEN) { // If not, can we fit it by moving any preceeding data flush up // against the beginning of the mbuf? if (pos + len <= KRBUF_MLEN) { ::memcpy(m->_dat, m->_data, m->_len); m->_data = m->_dat; } else { // If not, we'll have to split the mbuf data in half, the first // half being (pos) bytes in length, and the second half being // (m->_len - pos) bytes in length. Can we fit the second half // (which we're interested in) in the next mbuf? register MBuf* mNext = m->_next; int otherHalf = m->_len - pos; if (mNext->_len + otherHalf <= KRBUF_MLEN) { // It can fit, so can we do it without shifting anything in // that mbuf, i.e. will it fit, and will the peek window fit? int nextPos = (signed)(mNext->_data - mNext->_dat) - otherHalf; if (nextPos >= 0 && nextPos + len <= KRBUF_MLEN) { ::memcpy(mNext->_data - otherHalf, m->_data + pos, otherHalf); mNext->_data -= otherHalf; } else { ::memcpy(mNext->_dat + otherHalf, mNext->_data, mNext->_len); ::memcpy(mNext->_dat, m->_data + pos, otherHalf); mNext->_data = mNext->_dat; } mNext->_len += otherHalf; } else { // It won't fit, so we'll allocate a new mbuf, copy the // second half of the split into it, and proceed from there. mNext = mAlloc(); ::memcpy(mNext->_dat, m->_data + pos, otherHalf); mNext->_len = otherHalf; mNext->_next = m->_next; m->_next = mNext; } m->_len -= otherHalf; pos = 0; m = mNext; } } // Now we've got the space for the data we want, keep grabbing bits // of data until we have it all. Note because we've done our sums, we // can guarantee there's enough data in the mbuf's following, we just // have to get it here. This save silly checks for null pointers. while (pos + len > m->_len) { register MBuf* mNext = m->_next; // Can we copy the entire contents of the next mbuf? If so, // it's worth doing. Otherwise just copy what we can, and at that // point we will have everything. if ((unsigned)((m->_data - m->_dat) + m->_len + mNext->_len) <= KRBUF_MLEN) { ::memcpy(m->_data + m->_len, mNext->_data, mNext->_len); m->_len += mNext->_len; m->_next = mNext->_next; mFree(mNext); if (!m->_next) _mTail = m; } else { // Hmmm... should we copy all the data we can fit here, or just // that which we need to satisfy the requested size? The former // may prevent further shuffling in the future if we need to // peek at a larger portion of the same window, but if // we are peeking at distinct data structures the latter will // break the mbuf cleanly at one data structure, leaving the // next one in the next mbuf. Probably doesn't make that much // difference .... // int partial = KRBUF_MLEN - (m->_data - m->_dat) - m->_len; int partial = len - m->_len; ::memcpy(m->_data + m->_len, mNext->_data, partial); m->_len += partial; mNext->_data += partial; mNext->_len -= partial; break; } } return m->_data + pos; } //----------------------------------------------------------------------------- // void* KrBuf::getPartial(int& len, int pos); // // Return a pointer to a contiguous window of the KrBuf, of at most (len) // bytes, starting from (pos). No data is shuffled around, so only a partial // amount of the data requested may actually be contiguously visible (it may // overlap an mbuf boundary). Thus, the actual length available is returned // by reference to (len). If (len) is provided as 0, the maximum data // available is returned. // void* KrBuf::getPartial(int& len, int pos) { assert (pos >= 0 && pos < _size); register MBuf* m = _mHead; while (pos >= m->_len) { pos -= m->_len; m = m->_next; } len = len ? min(m->_len - pos, len) : (m->_len - pos); return m->_data + pos; } //----------------------------------------------------------------------------- // MBuf* KrBuf::insertRaw(int len, int& pos); // // Create space for (len) bytes of data starting at position (pos), or the end // if (pos) == KRBUF_END. Returns the mbuf and position within that mbuf where // inserted data can be written. // KrBuf::MBuf* KrBuf::insertRaw(int len, int& pos) { #ifdef KRBUF_DEBUG cerr << "KrBuf::insertRaw(len=" << len << ", pos=" << pos << ") " << this << " _size " << _size << " -> " << (_size + len) << endl; #endif if (len == 0) return NULL; assert (len > 0); register int chunk; register int remaining = len; register MBuf* m; MBuf* mTail; MBuf* mStart; if (pos == KRBUF_END || pos == _size) { mTail = NULL; m = mStart = _mTail; if (m) pos = m->_len; else pos = 0; } else { assert (pos <= _size); m = _mHead; MBuf** mPrev = &_mHead; while (pos > m->_len) { pos -= m->_len; mPrev = &(m->_next); m = *mPrev; } mStart = m; if (pos == 0) { mTail = m; m = NULL; } else if (pos == m->_len) { mTail = m->_next; } else { // Ok, we're splitting an mbuf down the middle. // if (KRBUF_MLEN - m->_len >= remaining) then we could // either split into two mbufs (bad space/good time), // or wedge the two bits of data apart in the same mbuf // (good space/bad time). We'll always split into two for // the moment, the rationale being that if an insertion // is needed here then there's a reasonable chance another // insertion will be needed here in the future, in which // case splitting has created new non-shuffle-requiring space. // Work out which side would be more efficient to copy out // to a new mbuf. if (pos > m->_len - pos) { // Copy the after data to a new mbuf mTail = mAlloc(); mTail->_next = m->_next; m->_next = mTail; if (!mTail->_next) _mTail = mTail; chunk = mTail->_len = m->_len - pos; mTail->_data = mTail->_dat + KRBUF_MLEN - chunk; ::memcpy(mTail->_data, m->_data + pos, chunk); m->_len = pos; } else { // Copy the before data to a new mbuf mTail = m; m = mAlloc(); m->_next = mTail; *mPrev = m; ::memcpy(m->_dat, mTail->_data, pos); m->_len = pos; mTail->_data += pos; mTail->_len -= pos; mStart = m; } } // Is there space at the beginning of the first tail mbuf? // If so, squeeze as much as we can there first. if (mTail->_data > mTail->_dat) { chunk = min(mTail->_data - mTail->_dat, remaining); mTail->_data -= chunk; mTail->_len += chunk; remaining -= chunk; if (!remaining) goto done; } } // Ok, we have split apart the mbuf chain at the insertion point, // and we have two chains - the before chain and the after chain. // mTail points to the after chain, and must be reattached after // the new data. The head mbuf in the after chain has been filled // above, we just need to fill the tail mbuf in the before chain, // and create new mbufs in between. if (!m) { m = _mHead = mStart = mAlloc(); } chunk = min(KRBUF_MLEN - m->_len - (m->_data - m->_dat), remaining); if (chunk) { m->_len += chunk; remaining -= chunk; } while (remaining) { m = m->_next = mAlloc(); chunk = min(KRBUF_MLEN, remaining); m->_len = chunk; remaining -= chunk; } m->_next = mTail; if (!mTail) _mTail = m; done: if (pos >= mStart->_len) { pos -= mStart->_len; mStart = mStart->_next; } // Now, the inserted space starts in (mStart), at (pos) bytes. // Do something with it. _size += len; return mStart; } //----------------------------------------------------------------------------- // void KrBuf::replaceAt(MBuf* m, const void* data, int len, int pos); // // Replace the range of bytes starting at (pos) relative to the mbuf (m), // length (len), with the data supplied. The total length remains unchanged. // void KrBuf::replaceAt(MBuf* m, const void* data, int len, int pos) { if (len == 0) return; while (pos >= m->_len) { pos -= m->_len; m = m->_next; } int chunk = min(m->_len - pos, len); ::memcpy(m->_data + pos, data, chunk); while (len -= chunk) { data = (char*)data + chunk; m = m->_next; chunk = min(m->_len, len); ::memcpy(m->_data, data, chunk); } } //----------------------------------------------------------------------------- // void KrBuf::setAt(MBuf* m, uchar c, int len, int pos); // // Set the range of bytes starting at (pos) relative to the mbuf (m), // length (len), to (c). The total length remains unchanged. // void KrBuf::setAt(MBuf* m, uchar c, int len, int pos) { if (len == 0) return; while (pos >= m->_len) { pos -= m->_len; m = m->_next; } int chunk = min(m->_len - pos, len); ::memset(m->_data + pos, c, chunk); while (len -= chunk) { m = m->_next; chunk = min(m->_len, len); ::memset(m->_data, c, chunk); } } //----------------------------------------------------------------------------- // void KrBuf::set(uchar c); // // Set every byte in the entire KrBuf to (c). The total length remains // unchanged. // void KrBuf::set(uchar c) { register MBuf* m = _mHead; while (m) { ::memset(m->_data, c, m->_len); m = m->_next; } } //----------------------------------------------------------------------------- // void KrBuf::remove(); // // Remove all data from the KrBuf. // void KrBuf::remove() { #ifdef KRBUF_DEBUG cerr << "KrBuf::remove() " << this << " _size " << _size << " -> 0" << endl; #endif if (_mHead) mFreem(_mHead); _mHead = _mTail = NULL; _size = 0; } //----------------------------------------------------------------------------- // void KrBuf::remove(int len, int pos); // // Remove (len) bytes from the KrBuf, starting from position (pos). // void KrBuf::remove(int len, int pos) { #ifdef KRBUF_DEBUG cerr << "KrBuf::remove(len=" << len << ", pos=" << pos << ") " << this << " _size " << _size << " -> " << (_size - len) << endl; #endif if (len == KRBUF_END) { len = _size - pos; assert (pos <= _size); } else assert (pos + len <= _size); if (len == 0) return; _size -= len; register MBuf* m = _mHead; register MBuf* mNext; MBuf* mPrev = NULL; while (pos >= m->_len) { pos -= m->_len; mPrev = m; m = m->_next; } // The start is somewhere within this mbuf. If the whole section // to be deleted is nestled within the data of the mbuf, then do // a block copy of the data to contract it down, else trim from // either end. if (pos) { if (pos + len < m->_len) { // pull data out of the middle of this mbuf, and finish ::memmove(m->_data + pos, m->_data + pos + len, m->_len - (pos + len)); m->_len -= len; return; } else { // trim data from the end of this mbuf, and continue // with the next mbuf len -= m->_len - pos; m->_len = pos; mPrev = m; m = m->_next; } } while (len) { // The beginning of this mbuf is included in the section to // be deleted. If the deleted section is larger than this mbuf, // then chop it out altogether, and continue with the next, else // just trim some bytes from the beginning. if (len >= m->_len) { len -= m->_len; mNext = m->_next; mFree(m); m = mNext; } else { m->_data += len; m->_len -= len; break; } } // Fix up the previous mbuf's pointer to this mbuf, or the head // if there's no previous one. if (mPrev) mPrev->_next = m; else _mHead = m; if (!m) _mTail = mPrev; } //----------------------------------------------------------------------------- // int KrBuf::read(int fd, int len); // // Attempt to read (len) bytes from the open file descriptor (fd), and append // the data to the end of the KrBuf. If (len) == 0 (the default), attempt to // read as much as possible (which is constrained to be IOV_MAX * KRBUF_MLEN). // Upon success, the number of bytes actually read is returned, otherwise // -1 is returned and errno is set appropriately. Upon end of file, 0 is // returned. Internally, readv(2) is used for efficiency. // int KrBuf::read(int fd, int len) { const int minimumBucketSize = 8; struct iovec iov[IOV_MAX]; int iovcnt = 0; assert (len >= 0); #ifdef KRBUF_DEBUG cerr << "KrBuf::read(fd=" << fd << ", len=" << len << ") " << this; #endif if (len == 0) len = IOV_MAX * KRBUF_MLEN; MBuf* m; MBuf* mStart = NULL; MBuf** mLastP = &_mHead; // See if there's worthwhile space at the end of the last mbuf to use // as the first iovec bucket, otherwise start with a fresh one. if (_mTail) { mLastP = &_mTail->_next; int remaining = KRBUF_MLEN - ((_mTail->_data - _mTail->_dat) + _mTail->_len); if (remaining >= minimumBucketSize) { mStart = _mTail; iov[iovcnt].iov_base = (caddr_t) (_mTail->_data + _mTail->_len); iov[iovcnt].iov_len = min(remaining, len); len -= iov[iovcnt].iov_len; iovcnt++; } } // Allocate a bunch of mbufs and point the scatter vector at them. while (iovcnt < IOV_MAX && len > 0) { m = mAlloc(); if (!mStart) mStart = m; *mLastP = m; mLastP = &m->_next; iov[iovcnt].iov_base = (caddr_t) (m->_dat); iov[iovcnt].iov_len = min(KRBUF_MLEN, len); len -= iov[iovcnt].iov_len; iovcnt++; } // Try reading ... #ifdef PURIFY_BUG // Use this to work around a Purify bug which thinks that // readv doesn't actually modify the data it's meant to be // writing to, therefore leaving it uninitialized ... int r = ::read(fd, iov[0].iov_base, iov[0].iov_len); #else // !PURIFY_BUG int r = ::readv(fd, iov, iovcnt); #endif // PURIFY_BUG if (r <= 0) { // If EOF or error, throw the allocated mbuf's away, and leave // everything else as it was. if (_mTail) { if (_mTail->_next) { mFreem(_mTail->_next); _mTail->_next = NULL; } } else { mFreem(_mHead); _mHead = NULL; } #ifdef KRBUF_DEBUG cerr << " -> " << r << endl; #endif } else { // Else work out how many mbuf's were filled with data, fix up // the lengths etc, and throw the unused mbufs away. m = mStart; int count = r; iovcnt = 0; while (count > 0) { m->_len += min(uint(count), iov[iovcnt].iov_len); count -= iov[iovcnt].iov_len; _mTail = m; m = m->_next; iovcnt++; } _mTail->_next = NULL; if (m) mFreem(m); _size += r; #ifdef KRBUF_DEBUG cerr << " _size " << (_size - r) << " -> " << _size << endl; #endif } return r; } //----------------------------------------------------------------------------- // int KrBuf::write(int fd, int len, int pos); // // Attempt to write (len) bytes from the KrBuf, starting at position (pos), // to open file descriptor (fd). If (len) == 0 (the default), attempt // to write as much as possible (which is constrained to be IOV_MAX * // KRBUF_MLEN). Upon success, the number of bytes written is returned. // Otherwise, -1 is returned and errno is set appropriately. Internally, // writev(2) is used for efficiency. // int KrBuf::write(int fd, int len, int pos) { struct iovec iov[IOV_MAX]; int iovcnt = 0; int chunk; assert(pos >= 0 && pos <= _size); if (pos == _size) return 0; if (len == 0) len = IOV_MAX * KRBUF_MLEN; len = min(len, _size - pos); register MBuf* m = _mHead; while (pos >= m->_len) { pos -= m->_len; m = m->_next; } while (len && iovcnt < IOV_MAX) { chunk = min(m->_len - pos, len); iov[iovcnt].iov_base = (caddr_t) (m->_data + pos); iov[iovcnt].iov_len = chunk; len -= chunk; pos = 0; iovcnt++; m = m->_next; } return ::writev(fd, iov, iovcnt); } //----------------------------------------------------------------------------- // int KrBuf::compare(const void* data, int len, int pos); // // Compare (len) bytes of data in the given buffer with data from the // KrBuf, starting at position (pos). The value returned will be -1, 0, or 1, // depending on whether the KrBuf data is lexicographically less than, equal // to, or greater than the supplied data. memcmp(3) is used to perform the // data comparison. // int KrBuf::compare(const void* data, int len, int pos) { if (len == KRBUF_END) len = _size - pos; if (len <= 0) return 0; register MBuf* m = _mHead; while (m && pos > m->_len) { pos -= m->_len; m = m->_next; } int chunk = min(m->_len - pos, len); int r = ::memcmp(m->_data + pos, data, chunk); if (r) return r; while (len -= chunk) { data = (char*)data + chunk; m = m->_next; chunk = min(m->_len, len); r = ::memcmp(m->_data, data, chunk); if (r) return r; } return 0; } #ifdef DEBUG //----------------------------------------------------------------------------- // void KrBuf::verify(); // // Verifies the integrity of the KrBuf. In particular, it walks the mbuf // list and ensures that each mbuf's size is both non-zero and within the // mbuf's limits. It accumulates the size of all mbufs and compares that // with the _size member. It also checks that the last mbuf traversed is // the same as that pointed to by the _mTail member. // // Only defined if DEBUG is defined at compile time. // void KrBuf::verify() { int size = 0, numBufs = 0; MBuf* m = _mHead; while (m) { numBufs++; assert (m->_len); assert (m->_data - m->_dat + m->_len <= KRBUF_MLEN); size += m->_len; if (!m->_next) break; m = m->_next; } assert (size == _size); assert (m == _mTail); printf("KrBuf::verify n=%d avg=%f ", numBufs, (float)_size / (float)numBufs); } //----------------------------------------------------------------------------- // void KrBuf::dump(bool printData); // // Dump the internal structure of a KrBuf, namely the list of all mbufs in // the list. A running byte position within the chain is maintained. If // the (printData) argument is true, the data contents of each mbuf is // also displayed. // // Only defined if DEBUG is defined at compile time. // void KrBuf::dump(bool printData) { printf("KrBuf(0x%08x) size=%d\n", (intptr_t)this, _size); int i, sp, pos = 0; MBuf* m = _mHead; while (m) { printf(" MBuf(0x%08x) pos=%6d len=%3d data=[0x%08x..0x%08x]\n", (intptr_t)m, pos, m->_len, (intptr_t)m->_data, (intptr_t)m->_data + m->_len - 1); if (printData) { sp = (m->_data - m->_dat) % 0x20 + 1; for (i=0; i_len; i++) { while (sp) { sp--; printf(" "); } printf("%02x ", m->_data[i]); if (i == m->_len - 1 || ((i + m->_data - m->_dat + 1) % 0x20) == 0) { printf("\n"); sp = 1; } } } pos += m->_len; m = m->_next; } } #endif //----------------------------------------------------------------------------- ////////////////////// above = new ///////// below = old ////////////////////////////////////////////////////////////////// #if 0 void* KrBuf::allocData(int size) { assert (size); if (size > KRBUF_MLEN) return NULL; _queueLen += size; _totalSent += size; register MBuf* m = _mTail; if (m) { if ((KRBUF_MLEN - m->_len) >= size) { // There's room in the tail mbuf, but do we need to // move the existing data down in order to fit it? if (KRBUF_MLEN - m->_len - (m->_data - m->_dat) < size) { ::memcpy(m->_dat, m->_data, m->_len); m->_data = m->_dat; } void* r = m->_data + m->_len; m->_len += size; return r; } else m = _mTail = m->_next = mAlloc(); } else m = _mTail = _mHead = mAlloc(); m->_len = size; return m->_data; } #endif